induction proof

Printable View

• Nov 1st 2008, 04: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 $\displaystyle b1,b2,b3...$
is a sequence defined as follows :$\displaystyle b1= 4 , b2 = 12$

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

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

Originally Posted by NidhiS
yea(Nerd)

not much to do here.

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

assume it is true for $\displaystyle n$

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

but $\displaystyle b_n$ and $\displaystyle b_{n - 1}$ are divisible by 4 by our inductive hypothesis, thus $\displaystyle 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, 04: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, 04: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, 04: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 $\displaystyle b_k$ for $\displaystyle 1 \le k \le n$, so the claim is true for $\displaystyle b_{k - 1}$ as well, so $\displaystyle b_{k - 1} = 4m$ for $\displaystyle m \in \mathbb{Z}$

thus, $\displaystyle b_{k + 1} = 4I + 4m = 4(I + m)$...
• Nov 1st 2008, 04: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, 04:26 PM
NidhiS
I mean b0 is not divisible by 4(Shake)
• Nov 1st 2008, 04:32 PM
Jhevon
Quote:

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

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