2

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?

Hugo
  • 45

2 Answers2

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

5xum
  • 123,496
  • 6
  • 128
  • 204
  • I should have clarified. I got $2^{k-1}$ by substituting in $k+1$ into the original equation. I'll edit OP. – Hugo Apr 08 '14 at 08:42
  • Okay, I made the edit to the original post. By substituting in $k+1$ into the equation, you end up with $2a_{k}+4a_{k−1}$, which is where I took the $k-1$ from. – Hugo Apr 08 '14 at 08:44
  • The last three lines of formulas are confuzing. Where did $$2^{k} | a_{k} + 2^{k-1}$$ come from?! – 5xum Apr 08 '14 at 08:49
  • Sorry, should be $2^{k} | a_{k} + 2a_{k-1}$. I'm really not that great at induction. It made sense when I did it before. – Hugo Apr 08 '14 at 08:53
  • Ah, so what you mean is that the first line follows from the second and third? Then, for the sake of clarity, I suggest you write it as: We know that $$2^k|2a_{k-1}.$$ Also, from $2^{k-1}|a_{k-1}$, it follows that $2^{k}|2a_{k-1}$. From these two facts, we conclude that $2^k|a_k+2a_{k-1}$.

    Writing it in this order makes sure that the people reading know which ste implies which. The idea, however, is quite correct.

     – 5xum Apr 08 '14 at 08:57
  • Great, thanks for helping me clarify it! I managed to confuse myself a bit there. – Hugo Apr 08 '14 at 09:00
  • That is why I advise you to always write your proof so you will immediatelly know which statements follows from which. If you do not, you risk confuzing the reader (and losing points on an exam), and worse, confuzing yourself. Always write notes for the future you, not for the present you. – 5xum Apr 08 '14 at 09:02
0

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.

Georgy
  • 1,467