Excuse the poor title, but my understanding is still a little fuzzy. Admins feel free to change it
Here is the question from the book.
suppose that $f_{0}, f_{1}, f_{2}...$ is a sequence defined as:
$f_{0} = 5, f_{1} = 16$
$f_{k} = 7f_{k-1} - 10f_{k-2}$ for all integers $k \geq 2$
Prove that $f_{n} = 3 * 2^n + 2 * 5^n$ for all integers $n \geq 0$
So, when I see this, here is more or less what is coming to my mind as how these are defined, and the implication is that for any positive integer input, f(x) == g(x)
f(x):
if x == 0: return 5
if x == 1: return 16
return 7 * f(x-1) - 10 * f(x-2)
g(x):
return 3 * 2^x + 2 * 5^x
This is mostly just how I am visualizing it.
So for the first two steps, I check the 0 and 1 against the g(x) function to confirm, and those work.
Next step is assuming that g(x) is the same as f(x). I imagine the next step is to do the inductive step of g(x) implies g(x+1), but I am a bit lost on the algebraic process of what comes next. Any ideas?
Thank you
According to the question, you already verified the base cases $0$ and $1$.
Now let $n\geq2$ and suppose the statement has been proved for $n-2$ and $n-1$, then $$f_n = 7f_{n-1}-10f_{n-2} \text.$$ Hence, from the induction hypotheses, $$f_n = 7(3\cdot 2^{n-1}+2\cdot 5^{n-1})-10(3\cdot 2^{n-2}+2\cdot 5^{n-2})$$ $$= 42\cdot2^{n-2}+70\cdot 5^{n-2}-30\cdot2^{n-2}-20\cdot5^{n-2}$$ $$= 12\cdot2^{n-2}+50\cdot 5^{n-2}$$ $$= 3\cdot 2^n+2\cdot 5^n \text.$$