Prove for all $ n\in \mathbb{N} $ ,$n ≥ 1, a(n)$ is odd.

Question

Prove for all $n\in\mathbb{N}\backslash \{0\}$, $a(n)$ is odd.

Consider the sequence defined as followed:

$a(1)= 1$

$a(2)= 3$,where $n \in \mathbb{N}$

$$a(n)=a(n-2)+2a(n-1), n ≥3$$ Conjecture:

$a(3) = 1+2(3) = 7$

$a(4)= 3+2(1+2(3))= 17$

$a(5)= 7+2(3+2(1+2(3)))=41$

I am unable to see a pattern in the above sequence to conjecture a formula to prove it by induction. Any assistance would be appreciated.

Answer 1

Easier method: proof via strong induction.

Base cases: $a(1)=1$ and $a(2)=3$ are both odd.

Induction hypothesis: All values of $a(k)$ for $1\leq k\leq n$ are odd for some $n$

We wish to show that this implies that $a(n+1)$ is also odd.

Indeed, since $a(n+1)=2a(n)+a(n-1)$, and $a(n-1)$ is odd by the induction hypothesis, we have $a(n-1)=2m+1$ for some $m\in \Bbb Z$ and therefore $a(n+1)=2(a(n)+m)+1$ is odd.

Thus, $a(n)$ is odd for all $n\geq 1$

---

Overkill method: actually coming up with a closed form expression for $a(n)$

Given the recurrence $a(n)=2a(n-1)+a(n-2)$, we look at the characteristic polynomial: $x^2-2x-1$

This factors as $(x-1-\sqrt{2})(x-1+\sqrt{2})$, implying that $a(n)=c_1 (1-\sqrt{2})^n+c_2 (1+\sqrt{2})^n$ for some values of $c_1$ and $c_2$.

Using the initial conditions, $a(1)=1$ and $a(2)=3$, we find $c_1=c_2=\frac{1}{2}$

That is to say

$$a(n)=\frac{1}{2}\left((1-\sqrt{2})^n+(1+\sqrt{2})^n\right)$$

Applying the binomial theorem:

$a(n)=\frac{1}{2}\sum\limits_{i=0}^n \binom{n}{i}[(-\sqrt{2})^i+(\sqrt{2})^i]=\frac{1}{2}\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n}{2i}[2\cdot 2^i]$

When $i$ is odd, the terms cancel out. When $i$ is even and at least $2$, the terms will add and be divisible by $4$ and thus still even after dividing by two. When $i$ is zero, the entry is $2$, which divided by two is one.

Thus, $a(n)=\frac{1}{2}(2+4(k))=1+2k$ for some $k$ and is therefore odd.

Answer 2

As a serious hint: you constantly add a odd number to an even one(cough 2a). Now just induct your way through it!

Answer 3

Hint:-$$a(n)-a(n-1)\equiv 0\pmod{2}$$Can you do the proof from here using Mathematical Induction?

Answer 4

By computation, $a(n)$ is odd for $1 \le n \le 5$.

Suppose there is an $n$ such that $a(n)$ is even.

Let $m$ be the smallest value of $n$ such that $a(n)$ is even. Then $m \ge 6$.

Then $a(m-2) =a(m)-2a(m-1) $ is also even. This contradicts the assumption that $m$ is the smallest such value.

Therefore there is no $m$ such that $a(m)$ is even, so all $a(n)$ are odd.