Prove by strong induction the Jacobstahl Series I am just beginning to learn about strong induction, I can't figure out how to complete this homework question:
Jacobstahl numbers are defined as
$$J_1 = 1$$
$$J_2 = 1$$
$$J_n = J_{n-1} + 2J_{n-2}$$
Prove:
$$J_n = 2^{n-1}-J_{n-1}$$
for n >= 2.
Here is what I have done so far:
Assume:
$$J_k = 2^{k-1} + J_{k-1}$$
then
$$J_{k+1} = 2^{k+0} - J_{k+0}$$
Then from the definition:
$$J_{k+1} = 2^{k+0} - J_{k+0} = 2^{k-1}-J_{k-1}+2(2^{k-2}-J_{k-2})$$
$$2^{k+0} - J_{k+0} = 2^{k-1}-j_{k-1}+2^1*2^{k-2} - 2^1*J_{k-2}$$
$$= 2(2^{k-1})-J_{k-1}-2J_{k-2}$$
$$= 2^{k+0} - J_{k-1}-2J_{k-2}$$
So I have gotten part of the way there, by finding the $2^{k+0}$ term, but I'm not sure what to do with the rest of it.  I think I've probably gone wrong in setting up the assumption, but I can't work out how.
 A: Your assumption for strong induction should be that $J_k=2^{k-1}-J_{k-1}$ for $k=2,\ldots,n$; from that assumption you want to prove that $J_{n+1}=2^n-J_n$. If you then attempt the usual kind of argument, your calculation of $J_{n+1}$ will start like this:
$$\begin{align*}
J_{n+1}&=J_n+2J_{n-1}\\
&=\left(2^{n-1}-J_{n-1}\right)+2J_{n-1}\\
&=2^{n-1}+J_{n-1}\\
&=2^{n-1}+2^{n-2}-J_{n-2}\,.
\end{align*}$$
It’s pretty clear that if you continue in the most straightforward fashion, replacing $J_{n-2}$ by $2^{n-3}-J_{n-3}$, you’ll still have a $J_k$ term of some kind: you’re not obviously reaching what you want.
It actually is possible to get somewhere this way, but for a simple induction proof you’re better off looking at the desired relationship in a different way. Notice that $J_k=2^{k-1}-J_{k-1}$ is equivalent to $J_k+J_{k-1}=2^{k-1}$. Thus, we could just as well assume as our induction hypothesis that $J_k+J_{k-1}=2^{k-1}$ for $k=2,\ldots,n$ and try to prove that $J_{n+1}+J_n=2^n$. Then
$$J_{n+1}+J_n=J_n+2J_{n-1}+J_n\,;$$
now just simplify that and apply the induction hypothesis. (You’ll find that you don’t actually need strong induction here: ordinary induction is enough.)
