Properties of a recursively-defined sequence using induction This is a homework problem. Not expecting the solution, just a nudge in the right direction!
$N$ is a function defined inductively as follows:
$$N(1) = N(2) = N(3) = 1$$
$$N(n) = N(n−1) + N(n−3) \quad \text{for } n > 3.$$

a. Prove by induction on $a$, $$N(n) = N(a+2)N(n−1−a) + N(a)N(n−2−a) + N(a+1)N(n−3− a)$$
  for $a > 0$ and $n > a + 3$. (Assume $N(0) = 0$).

Induction on "$a$". :O So lost! :'(

b. Assuming the fact from part (a), prove that
  $$N(2k) = N(k)N(k) + 2N(k)N(k−2) + N(k−1)N(k−1)$$ and
  $$N(2k−1) = N(k)N(k) + 2N(k−1)N(k−2)$$
c. Find similar formulas for $N(2k+1)$ and $N(2k+2)$ in terms of $N(k)$, $N(k−1)$,
  and $N(k−2)$.


(a.1) Basis ($a=1$): you assume $n>4$ and:
$$
N(3)N(n-2) + N(1)N(n-3) + N(2)N(n-4) = N(n-2) + N(n-3) + N(n-4)
=N((n-1) - 1) + N((n-1)-3) + N(n-3) = N(n-1) + N(n-3) = N(n)
$$
Obs: you can check manually the case $n=4$ where the induction formula is not guaranteed to work using $N(0)=0$.
(a.2) Inductive step: assume the formula works for $a$, and as usual, assume $n>a+3$. We work on $a+1$:
$$
N(a+3)N(n-2-a) + N(a+1)N(n-3-a) + N(a+2)N(n-4-a) = \\ 
=N((a+2)+1)N((n-1-a)-1) + N((a)+1)N((n-2-a)-1) + N((a+1)+1)N((n-3-a)-1)
$$
which we want to show it's still $N(n)$. We can approach it in parts. From the recurrence of the function, we know that $N(n+1) = N(n)+N(n-2)$ and $N(n-1) = N(n)-N(n-3)$. We have 3 product blocks, so let's open up each one:
1. > $(N(a+2) + N(a))(N(n-a-1)-N(n-a-4))$.
2. > $(N(a) + N(a-2))(N(n-2-a) - N(n-a-5))$.
3. > $(N(a+1) + N(a-1))(N(n-3-a)-N(n-a-6))$.
Note that, when you distribute these products, the first term on each of them adds up to $N(n)$ by the induction hypothesis. So, you're left to prove that the sum of the remaining terms is $0$, and believe me, you can. It's pretty gross, so I'm not doing it here (took one A4 page), but multiply them up and use the two recurrence relations I mentioned above and you can check that they actually cancel each other. It's messy, but not hard.
(b) Pick $a=k-2$, and let's apply the formula from the previous item:
$$
N(2k) = N(k)N(k+1) + N(k-2)N(k) + N(k-1)N(k-1) = \\
= N(k)(N(k) + N(k-2)) + N(k-2)N(k) + N(k-1)N(k-1) = \\
N(k)N(k) + 2N(k)N(k-2) + N(k-1)N(k-1),
$$
as desired. For the second formula, again, pick $a=k-2$, and the expression yields:
$$
N(2k-1) = N(k)N(2k-2-k+2) + N(k-2)N(2k-1-2-k+2) + N(k-1)N(2k-1-3-k+2) = \\
= N(k)N(k) + 2N(k-1)N(k-2).
$$
(c) For $N(2k+1)$, pick $a=k-1$. Applying the formula, we have:
$$
N(2k+1) = N(k+1)N(k+1) + 2N(k-1)N(k) = \\
= (N(k)+N(k-2))^{2} + 2N(k-1)N(k).
$$
Finally, for $N(2k+2)$, note that we have a formula for $N(2k)$. Apply that for $2(k+1)$, and we have:
$$
N(2k+2) = N(2(k+1)) = N(k+1)N(k+1) + 2N(k+1)N(k-1) + N(k)N(k) = \\
=(N(k)+N(k-2))^{2} + 2N(k-1)(N(k) + N(k-2)) + (N(k))^{2}
$$
which are all in terms of $N(k),N(k-1)$ or $N(k-2)$, and you can expand it further if you want.
