# Solving linear recurrence by induction

Heres the "Link", my issue circled in red. Can anyone tell me how they get this this step?; How does $6s_k = 6(5^k-1)$? What rule are they using here?

$s_{k+1} = 6s_k - 5s_{k-1} = 6(5^k -1)-5(5^{k-1}-1)$

Thanks everyone! -Kyle

-
First: No need to sign your name: stackexchange automatically adds a signature on the bottom right. Second: Titles are not meant to be greeting lines. They should be descriptive of the content, informative, and help organize the site. –  Arturo Magidin Mar 14 '11 at 19:04

$s_i = 5^i - 1$ by inductive hypothesis (i.e. you are assuming this now), so
$s_k = 5^k - 1$

That's it!

-

They use the property $P(n)$ they defined at the top of that page.

This is known as the "induction hypothesis." The form of argument that induction takes is to prove a very simple "base" case ($P(0)$ and $P(1)$ here), and then make one more generalized argument that, if $P(n)$ holds (or, for strong induction as done here, $P(k)$ holds for all $k\le n$), then $P(n+1)$ holds. This means that, when proving $P(n+1)$, you can use $P(n)$ (which, in this case, is the fact that $s_k = 5^k - 1$). Finally, you say that because you can just "keep doing this" to get to any $n$, the hypothesis holds for all $n$. To go any deeper, you need a bit of set theory.

-

Just compute. You have $6S_{k}-5S_{k-1}= 6(5^{k}-1) - 5(5^{k-1}-1)=6\cdot 5^{k}-5^{k}-6+5=5^{k+1}-1=S_{k+1}$

-