# induction proof

• Nov 1st 2008, 05:03 PM
NidhiS
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 (Thinking)

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
(Wondering)

Thanks
• Nov 1st 2008, 05:15 PM
Jhevon
Quote:

Originally Posted by NidhiS
yea(Nerd)

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
• Nov 1st 2008, 05:15 PM
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-2
we know that bk is divisible my 4
such that bk = 4l for some integer l

then what next?
• Nov 1st 2008, 05:19 PM
NidhiS
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.(Happy)
• Nov 1st 2008, 05:20 PM
Jhevon
Quote:

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)$...
• Nov 1st 2008, 05:25 PM
NidhiS
well i think you over generalized the proof ,in a way.

er what if k=1 then b 1 = 4l but b0 is not.(Wondering).
• Nov 1st 2008, 05:26 PM
NidhiS
I mean b0 is not divisible by 4(Shake)
• Nov 1st 2008, 05:32 PM
Jhevon
Quote:

Originally Posted by NidhiS
I mean b0 is not divisible by 4(Shake)

$b_0$ doesn't exist, the first term of your sequence is $b_1$