prove that recurrence relation is odd
Hello!
I just want to be sure if I did solve the task correctly.
The task is:
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.
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.
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?
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.