How to prove this statement with "first" principle of Mathematical induction and not strong Mathematical induction?

Question

Define a sequence $s_0,s_1,s_2,...$ as follows : $$s_0=0, s_1=4, s_k=6s_{k-1} - 5s_{k-2} \; \forall \; \text{integers} \; k\ge 2.$$ Prove by Principle of strong mathematical induction that $$s_n=5^n-1 \; \forall \; n\ge 0.$$

It's very easy to prove this by strong mathematical induction. However I am interested in proving this by "first" principle of mathematical induction only. Any ideas?

Answer 1

$$s_k-s_{k-1}=5(s_{k-1}-s_{k-2}),$$ which says that $$s_k-s_{k-1}=4\cdot5^{k-1}$$ for all $k\geq1$.

Now, we can use an induction, which you wish.

For $k=0$ and for $k=1$ it's true.

Let $s_k=5^k-1$ for all $k\geq0$.

Thus, $$s_{k+1}=s_k+4\cdot5^k=5^k-1+4\cdot5^k=5^{k+1}-1.$$ Done!

Answer 2

It seems I have got my answer. I saw a proof that "first" principle of mathematical induction and the strong principle of mathematical induction are equivalent. So by that proof I have formulated a proof for this one too. Here it goes :

Let $P(n) : s_n=5^n-1$

Let $Q(n) : P(j) \; \text{is true} \; \forall \; 0\le j\le n.$ We will use $Q(n)$ for using "first" principle of mathematical induction.

Basis step : We show that $Q(1)$ is true i.e. $P(1)$ and $P(2)$ are true statements.

Here $s_0=5^0-1=0$ which agrees with the definition $s_0=0.$ and $s_1=5^1-1=4$ which also agrees with the definition $s_1=4$.

Inductive step : Suppose $Q(k)$ is true for any integer $k \ge 1.$ i.e. $P(j) \; \text{is true} \; \forall \; 0\le j \le k$ for any integer $k\ge 1$.

Consider $s_{k+1}=6s_k - 5s_{k-1}.$

Then $s_{k+1}=6(5^k-1)-5(5^{k-1} -1)=6.5^k-6-5^k+5=5^{k+1}-1.$ Which was to be proved.