Prove for all $ n\in \mathbb{N} $ ,$n ≥ 1, a(n)$ is odd. 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.
 A: Hint:-$$a(n)-a(n-1)\equiv 0\pmod{2}$$Can you do the proof from here using Mathematical Induction?
A: 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.
A: As a serious hint: you constantly add a odd number to an even one(cough 2a). Now just induct your way through it!
A: 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.
