Q$4$ Problem $4$

$20$ Points

On a NEW SHEET of paper, write your name and the heading Problem $4.$ Answer this question on that sheet of paper $($and another sheet if needed$).$

Let $a_0=1,a_1=1,$ and, for $i>0,a_{i+1}=a_i+2a_{i-1}.$ Prove by induction that for all $n>0,$ if $n$ is even, then $a_n=2a_{n-1}+1,$ and if $n$ is odd, then $a_n=2a_{n-1}-1.$

Hint: The inductive step is best proven by cases.