# Proof By Induction Recurrance Questions, Answers and Solutions

a - answer    s - solution    v - video    d - discussion

## Question 1

Prove:

a) $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

b) $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

c) $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

d) $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

e) $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

## Question 2

Prove

a) A term in the Fibonacci Sequence can be calculated by the formula $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.a s v d