Question about induction

Question

Prove by induction $w_k = w_{k−2} + k$, for all integers $k \ge 3, w_1 = 1,w_2 = 2$ has an explicit formula $$ w_n = \begin{cases} \frac{(n+1)^2}{4}, & \text{if $n$ is odd} \\ \frac n2(\frac n2 + 1), & \text{if $n$ is even} \end{cases}$$

Inductive step for when $n$ is odd:

Suppose $w_k = \frac{(k+1)^2}{4}$ if $k$ is odd. Then by definition of $w$, we have $w_{k + 2} = w_k + k + 2 = \frac{(k+1)^2}{4} + k + 2 = \frac {k^2 + 2k + 1}{4} + k + 2= \frac {k^2 + 6k + 8}{4} = \frac {(k +3)^2}{4} $ if $k + 2$ is odd.

Is it important that we prove $w_{k + 1} = \frac{(k+2)^2}{4}$ if $k + 1$ is odd or is the proof for $w_{k + 2} = \frac{(k+3)^2}{4}$ if $k + 2$ is enough?

Answer 1

The beginning is clear. After that, for the (strong) induction step, you want to show that $w_n$ is given by the formula specified, provided this is the case for $w_1,w_2,\ldots, w_{n-1}$. By the nature of the recursion, we need only that the formula holds for $w_{n-2}$ (which is among the given $w_i$ because we also assume $n>2$ for the induction step!). AS $n-2$ has the same parity as $n$, we conclude that $$w_n=w_{n-2}+n=\begin{cases}\frac{(n-2+1)^2}{4}+n,&\text{if $n$ and $n-2$ are odd}\\\frac{n-2}2(\frac{n-2}2+1)+n,&\text{if $n$ and $n-2$ are odd}\end{cases} $$ Simple transformations should bring the desired result ...