# Proof by induction

1. Oct 13, 2016

### Arew

1. The problem statement, all variables and given/known data
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}$$

2. Relevant equations

3. The attempt at a solution

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?

If none of the above makes sense, can I please get help getting started with the inductive step.

2. Oct 13, 2016

### PeroK

It's fine to here. That's the odd numbers sorted out. Now, what about the even numbers?

3. Oct 13, 2016

### Staff: Mentor

And the induction base? You have to verify this, too. It is really important and not just something annoying.
And what if k is even?
(Remark: there is a typo.)

4. Oct 13, 2016

### Arew

Thanks for the comments. Do we have to handle $$w_{k+1}$$ at all?

5. Oct 13, 2016

### PeroK

Why would you?

6. Oct 13, 2016

### Arew

I was worried we proved w_k for every other integer k. I see why that's wrong. Thanks.

7. Oct 13, 2016

### Staff: Mentor

With the induction base (two values), the odd numbers, which are covered by $k \rightarrow k+2$, only the even are missing. What other numbers can you think of?

8. Oct 13, 2016

### Arew

Can't think of anything else :) Thanks.