0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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 ...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @ Hagen von Eitzen, can you please give me an example of transformation? I keep coming up wrong. $\endgroup$ – Wyu Oct 13 '16 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.