Proof by induction for divisibility by power of 2^n

Question

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?

Answer 1

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}$.

Answer 2

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.