Prove that $S_n = 5^n - 1$

Question

Use Strong Induction:

$s_0 = 0 $, $s_1 =4$ and $s_n= 6s_{n-1} - 5s_{n-2}$ for all $n\in \mathbb{N} \setminus \{1\}$

Prove that $S_n = 5^n - 1$

In regards to the first step, can I start at n=2? Not sure where to begin on this one.

Answer 1

For the base case, you should start with computing $s_2$ using both methods and showing they're the same.

That is, $s_2 = 6\cdot 4 -5\cdot 0 = 24 = 5^2 - 1$.

For the inductive step, you use strong induction by assuming the closed form holds for all indices up to a certain $n$ (meaning it also holds for $n-1$ and $n$), and then show that it holds for $n+1$ as well.

That is,

Assume $s_{n-1} = 5^{n-1}-1$ and $s_n = 5^n-1$.

Now use $s_{n+1} = 6s_n - 5s_{n-1}$ and manipulate the result so that you get $s_{n+1} = 5^{n+1}-1$.

Answer 2

Sure is. $S_2 = 6S_1 - 5S_0 = 6\cdot 4 - 5\cdot 0 = 24 = 5^2 - 1$, assume $S_k = 5^k - 1, \forall k$ such that $2 \leq k < n$. We have: $S_n = 6S_{n-1} - 5S_{n-2} = 6\cdot (5^{n-1} - 1) - 5\cdot (5^{n-2} - 1) = 6\cdot 5^{n-1} - 6 - 5^{n-1} + 5 = 5\cdot 5^{n-1} - 1 = 5^n - 1$.

Answer 3

In this case, there is an ad hoc way.

Note that $s_n= 6s_{n-1} - 5s_{n-2}$ iff $s_n-s_{n-1}= 5s_{n-1} - 5s_{n-2} = 5(s_{n-1} - s_{n-2})$.

So, if you set $u_n =s_n-s_{n-1}$, then $u_n = 5 u_{n-1}$, which is easy to solve: $u_n = 5^{n-1} u_1$, and $u_1=s_1-s_0=4$. Thus, $u_n = 4\cdot 5^{n-1}$.

Then, $s_n-s_0 =u_n+\cdots+u_1 = 4\cdot (5^{n-1}+5^{n-2}+\cdots+5+1)=4\cdot\dfrac{5^n-1}{5-1}=5^n-1$.