Proof by induction for divisibility by power of 2^n I'm trying to prove, using strong induction, that $2^n$ divides $a_{n}$ where:
$$a_{n} = 2a_{n-1} + 4a_{n-2}$$ 
Given that $a_{1} = 2$ andn $a_{2} = 8$
What I've got so far:
Base Case
$$n = 1$$
$$a_{1} = 2$$
$$2^{1} | 2$$
$$n = 2$$
$$a_{2} = 8$$
$$2^{2} | 8$$
Induction steps
For some positive integer $k \geq 1$, assume that $2^k$ divides $a_{k} = 2a_{k+1} + 4a_{k-2}$ because $2^1$ divides $a_1$ and $2^2$ divides $a_2$.  
We will prove that $2^{k+1}$ divides $a_{k+1}$
$$a_{k+1} = 2a_{(k+1)-1} + 4a_{(k+1)-2}$$
$$ = 2a_{k} + 4a_{k-1}$$
Assume: if $a$ divides $b$ and $a$ divides $c$, therefore $a$ divides $b+c$:
$$2^{k} | a_{k} + 2a_{k-1}$$
$$2^{k} | 2a_{k-1}$$
$$2 \times  2^{k-1} | 2a_{k-1}$$ 
(which is equal to $4a_{k-1}$)
Therefore $2^{k-1} | a_{k-1}$.
I'm just looking for a little guidance. Does this make sense?
 A: What you did was assume that $2^k$ divides $a_k$ and proved that $2^{k-1}$ divides $a_{k-1}$. What you should have done is assume that $2^k$ divides $a_k$ and prove that $2^{k+1}$ divides $a_{k+1}$.
A: Ordinary induction to prove a statement $P_n \forall n \in \mathbb{N}$ consists of two steps: {Proving $P_1$} and {show that $P_{k-1} \Rightarrow P_k$ for $k=2,3,\dots$}. Sometimes however you don't have enough information for the second step. This is where strong induction comes in, which is slightly different in our case: {Prove $P_1$ and $P_2$} and now {show that $\{P_1,P_2, \dots P_{k-1}\} \Rightarrow P_k$ for $k=3,4,\dots$}. In principle they are equivalent but in practice the job of proving $P_k$ becomes easier if you have more assumptions. So here we go:
$$P_n=\{2^n|a_n\}$$
Obviously $P_1$ and $P_2$ are true as you noted. We now assume $P_{k-2}$ and $P_{k-1}$, where $k=3,4, \dots$ and we want to show $P_k$. We have $2^{k-2}|a_{k-2} \implies a_{k-2}=2^{k-2}\alpha$ and similarly $a_{k-1}=2^{k-1} \beta$, where $\alpha$ and $\beta$ are integers. But now $$a_k=2a_{k-1}+4a_{k-2}=2^k \beta+2^k \alpha=2^k(\alpha+\beta)$$
i.e. $2^k|a_k$ and we 're done. So it's really a "nothing" proof if you put it in the right context.
