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.