# prove that recurrence relation is odd

• Sep 13th 2011, 07:07 AM
p0oint
prove that recurrence relation is odd
Hello!

I just want to be sure if I did solve the task correctly.

Prove that bn is odd for integers n>=1

\$\displaystyle b_1=1\$
\$\displaystyle b_2=3\$
\$\displaystyle b_k=b_{k-2}+2b_{k-1}\$ for k>=3

The attempt at a solution

Induction basis:

\$\displaystyle b_1=1\$ true 1 is odd
\$\displaystyle b_2=3\$ true 2 is odd

Now the question is:

Could I use the strong (complete) induction?

If I can use it, the solution is simple:

Let the recurrence relation is true for all k, such that n<k and n=k i.e n<=k
\$\displaystyle b_k=b_{k-2}+2b_{k-1}\$

then for n=k+1

\$\displaystyle b_{k+1}=b_{k-1}+2b_{k}\$

\$\displaystyle b_{k-1}\$ is odd and \$\displaystyle 2b_k\$ is even therefore odd+even=odd

Is this correct?

Thank you.

Regards.
• Sep 13th 2011, 01:15 PM
emakarov
Re: prove that recurrence relation is odd
Quote:

Originally Posted by p0oint
Let the recurrence relation is true for all k, such that n<k and n=k i.e n<=k
\$\displaystyle b_k=b_{k-2}+2b_{k-1}\$

then for n=k+1

\$\displaystyle b_{k+1}=b_{k-1}+2b_{k}\$

\$\displaystyle b_{k-1}\$ is odd and \$\displaystyle 2b_k\$ is even therefore odd+even=odd

You assume that the property you need to prove, i.e., that \$\displaystyle b_n\$ or \$\displaystyle b_k\$ is odd, and not the recurrence relation, holds for all previous n or k. Secondly, do you mean it is true for all n (instead of k) such that n <= k? Perhaps you could rewrite the induction step more carefully.
• Sep 14th 2011, 02:03 AM
p0oint
Re: prove that recurrence relation is odd
Hello!

Yeah I messed the things a little bit.

I meant if P(1) is true and for every integer k>=1 P(1), P(2), ... , P(k) imply P(k+1) then P(n) is true for all n>=1

Is this ok?
• Sep 14th 2011, 02:24 AM
emakarov
Re: prove that recurrence relation is odd
Quote:

I meant if P(1) is true and for every integer k>=1 P(1), P(2), ... , P(k) imply P(k+1) then P(n) is true for all n>=1
This is correct.