Suppose the following
$$ f(0)= 0$$
$$ f(1)=2$$
$$ f(n)= 4f(n-1)-3f(n-2)$$
I want to prove that
$$f(n)= 3^n -1$$
by induction.
I started by trying this
$$f(n+1)=4f(n)-3f(n-1)$$
Which gives me this:
$$ f(n+1)= 4(3^n-1)-3f(n-1)$$
However I do not understand how the second part
$$3f(n-1)%$$
of the term is solvable. Can someone give me some pointers on how to solve this?
HINT
You are probably used to the inductive scheme where you go from $P(n)$ to $P(n+1)$, where $P(n)$ is some claim about the number $n$.
That is, once you show the base $P(0)$, and you have also shown that $P(n)\to P(n+1)$, you have shown $P(n)$ for all $n$:
You have shown $P(0)$
But given $P(0)$ and $P(n)\to P(n+1)$, this means $P(1)$
But given $P(1)$ and $P(n)\to P(n+1)$, this means $P(2)$
But given $P(2)$ and $P(n)\to P(n+1)$, this means $P(3)$
Etc.
OK, so that's a very 'typical' form of induction.... where each 'domino stone' knocks over the next.
However, in this case, each domino stone needs not just the very previous domino stone to fall over, but the previous two ... you can immediately see this by the fact that the recursive function refers to the previous two terms .. and that the sequence starts with two base cases.
Thus, what you need to show is that $P(n-1)$ and given that $P(n)$, you can show $P(n+1)$
Also, there are now two base cases. That is, also show that $P(0)$ and that $P(1)$
With that, the claim $P(n)$ should hold for any $n$, because:
You have shown $P(0)$ and $P(1)$.
But given $P(0)$ and $P(1)$ and $(P(n-1) \land P(n)) \to P(n+1)$, this means $P(2)$
But given $P(1)$ and $P(2)$ and $(P(n-1) \land P(n)) \to P(n+1)$, this means $P(3)$
But given $P(2)$ and $P(3)$ and $(P(n-1) \land P(n)) \to P(n+1)$, this means $P(4)$
Etc.
So, applied to your problem, you need to show that $f(n+1)=3^{n+1}-1$ if you assume that:
$f(n)=3^{n}-1$ and $f(n-1)=3^{n-1}-1$
And, for the base, you need to show that $f(n)=3^{n}-1$ for $n=0$ and $n=1$