# Math Help - induction proof

1. ## induction proof

I need some help with this induction proof.I'm like stuck at a crucial point and don't know how to get past it and complete the proof

The question says:

Suppose $b1,b2,b3...$
is a sequence defined as follows : $b1= 4 , b2 = 12$

$bk = bk-1 + bk-2$for all integers $k>= 3$
prove that bn is divisible by 4 for all integers n>=1

Thanks

2. Originally Posted by NidhiS
yea
not much to do here.

clearly it is true for $n = 1$, since $b_1 = 4$ which is divisible by 4

assume it is true for $n$

then $b_{n + 1} = b_n + b_{n - 1}$

but $b_n$ and $b_{n - 1}$ are divisible by 4 by our inductive hypothesis, thus $b_{n + 1}$ is divisible by 4, since it is the sum of two numbers divisible by 4

the proof is complete

of course you should clean up the proof, it is more of an outline. but i did more than half the work for you

3. This is what I did:

lets assume that p(k) is divisible by 4 (INDUCTIVE HYPOTHESIS)
so p(k) : bk = bk-1 + bk-2

we have to show that p(k+1) is divisible my 4.

p(k+1) : bk+1 = bk + bk-2
we know that bk is divisible my 4
such that bk = 4l for some integer l

then what next?

4. er thanks! that actually helped .Let me go back and flip through the pages and see which theorem cna be used to justify this proof.

5. Originally Posted by NidhiS
This is what I did:

lets assume that p(k) is divisible by 4 (INDUCTIVE HYPOTHESIS)
so p(k) : bk = bk-1 + bk-2

we have to show that p(k+1) is divisible my 4.

p(k+1) : bk+1 = bk + bk-1
we know that bk is divisible my 4
such that bk = 4l for some integer l

then what next?
by the hypothesis, it is true for every $b_k$ for $1 \le k \le n$, so the claim is true for $b_{k - 1}$ as well, so $b_{k - 1} = 4m$ for $m \in \mathbb{Z}$

thus, $b_{k + 1} = 4I + 4m = 4(I + m)$...

6. well i think you over generalized the proof ,in a way.

er what if k=1 then b 1 = 4l but b0 is not..

7. I mean b0 is not divisible by 4

8. Originally Posted by NidhiS
I mean b0 is not divisible by 4
$b_0$ doesn't exist, the first term of your sequence is $b_1$