1

$$a_1=0, a_2=2, a_3=2, ... a_k = a_{k-2}+3a_{k-3}$$ for k $\ge$ 4

Initial case n = 1 given above it is true as zero is divisible by 2.

Let n = k. Assume that $a_{k+1} = a_{k-2+1}+3a_{k-3+1} $

That is $a_{k+1} = a_{k-1}+3a_{k-2} $

How to prove by induction that $a_n$ is even for n $\ge$ 1

Evan S
  • 75
  • 1
  • 1
  • 6

3 Answers3

1

All $a_i$ for $i\in\{1,2,3\}$ are even. Note that sum of even is even.

evil999man
  • 6,018
  • Do it one by one? You meant plug 1 to 4 each into k? If that is the way I will only need to work out with 4 since 1,2,3 are all given. Am I correct? – Evan S May 05 '14 at 05:08
  • @EvanS Yes. you know that $a_{k-2}$ and $a_{k-3}$ are even, – evil999man May 05 '14 at 05:10
  • To conclude proof by induction, would it be sufficient to say that "Note that the sum of even is even and even number times 3 is also even. We know that $a_{k-1}$ and $a_{k-2}$ are even. Thus it is true" – Evan S May 05 '14 at 05:18
1

Use strong induction on $n \geq 1$.

Check the base case: $n = 1$, then $a_1 = 0 = 0\cdot 2$: even

Supposed the claim is true for all $k < n$, that is: $2|a_k$ for $k < n$, you need to show:

$2|a_n$.

Since $n - 2 < n$, and $n - 3 < n$, the induction hypothesis states that: $2|a_{n-2}$ and also $2|a_{n-3}$, so $2|(a_{n-2} + 3\cdot a_{n-3}) = a_n$.

So: $2|a_n$ ,$\forall n \geq 1$

DeepSea
  • 77,651
0

Let $a_i=2.b_i$ for all $i<k$, then $a_k=a_{k-2}+3.a_{k-3}=2.b_{k-2}+2.3.b_{k-3}=2.b_k$.