let $a_n$ be defined as :
$a_0 = a_1 = 1$
$a_n = 2a_{n-1} + a_{n-2} , n<=2$
prove that every n ∈ N U {0} , $a_n$ will be odd
I tried to prove it with induction, but got stuck and couldn't continue
Base checks: n=2: $a_n=2a_{n-1} + a_{n-2} = 2a_1 + a_0 = 3$
n=3: $a_n=2a_{n-1} + a_{n-2} = 2a_2 + a_1 = 6+1=7$
Assume for n : $a_n=2*(2k+1)+(2k+1)$
Show for n+1 :$a_{n+1}=2a_{n+1-1}+a_{n+1-2}=2a_n+a_{n-1}=2*(2a_{n-1}+a_{n-2})+a_{n-1}=4a_{n-1}+2a_{n-2} +a_{n-1}=3a_{n-1}+2a_{n-2}$
Looking forward for your help
There is no need to check $n=2$ or $n=3$. You already have the base cases. Just observe that $2x+y$ is odd if $y$ is odd. However, it's the term two steps lower, in your case, so the idea is to use complete induction.
The cases $n=0$ and $n=1$ are true by assumption.
Suppose the statement holds for every $m<n$, where $n>2$ (this is the complete induction hypothesis). Then $$ a_{n}=2a_{n-1}+a_{n-2} $$ Since $2a_{n-1}$ is even and $a_{n-2}$ is odd (by induction hypothesis), also $a_n$ is odd.
Alternatively, you can observe that $a_{n+2}\equiv a_{n}\pmod{2}$. So you can prove by simple induction that $a_{2m}\equiv 1\pmod{2}$ and $a_{2m+1}\equiv 1\pmod{2}$; thus every even- an odd-indexed term is odd.