Question about induction when considering odd and even cases

[Ozma]

I was trying to prove by induction that
$$\sum_{n=0}^k (-1)^n =\begin{cases} 1, \ \text{if} \ k \ \text{is even} \\ 0, \ \text{if} \ k \ \text{is odd} \end{cases} ..... edited$$I distinguished two cases, $k$ even and $k$ odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer $n_0$, assume it holds for $n \ge n_0$ with $n$ non negative integer and shows that this assumption implies that it holds for $n+1$; we conclude that the property holds for any $n \ge n_0$.

However, if I assume $k$ even, it works for $k=0$ but when I have to prove that it works for $k+1$ I get that, since $k$ is even, is odd and hence I can't prove that this holds for all even $k$ because I am proving it for an odd number. So, intuitively I get that I must show that, for instance, it holds for an even $k_0$, assume it holds for a generic even $k$ and show that this implies it holds for the next even number $k+2$. And this works, similarly it works for the odd case. The question is: why the standard induction definition seems not to work here, that is, the one replacing $n$ with $n+1$? I thought that I can write an even number $k=2m$ with $m$ non negative integer and use "classical" induction with $m+1$, but I should work on $k$ and not on $m$. What is happening here?

 

[pka]

Why not just use $k\mod 2~~?$
Or look HERE

 

[Steven G]

Show that the statement is true for k=0. Assume it true for k=2m. Then show it is true for for k = 2m+2. This will take care of the evens.
Then do the same for the odds. Show true for k=1, etc

 

[Dr.Peterson]

I was trying to prove by induction that
$$\sum_{n=0}^k (-1)^n =\begin{cases} 1, \ \text{if} \ k \ \text{is even} \\ 0, \ \text{if} \ k \ \text{is even} \end{cases}$$I distinguished two cases, $k$ even and $k$ odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer $n_0$, assume it holds for $n \ge n_0$ with $n$ non negative integer and shows that this assumption implies that it holds for $n+1$; we conclude that the property holds for any $n \ge n_0$.

However, if I assume $k$ even, it works for $k=0$ but when I have to prove that it works for $k+1$ I get that, since $k$ is even, is odd and hence I can't prove that this holds for all even $k$ because I am proving it for an odd number. So, intuitively I get that I must show that, for instance, it holds for an even $k_0$, assume it holds for a generic even $k$ and show that this implies it holds for the next even number $k+2$. And this works, similarly it works for the odd case. The question is: why the standard induction definition seems not to work here, that is, the one replacing $n$ with $n+1$? I thought that I can write an even number $k=2m$ with $m$ non negative integer and use "classical" induction with $m+1$, but I should work on $k$ and not on $m$. What is happening here?

I might restate each case in terms of a new variable, say m, so that for even k, we define k = 2m, and for odd k, we define k=2m+1. Then perform induction, for each case, on m.

 

[Harry_the_cat]

I was trying to prove by induction that
$$\sum_{n=0}^k (-1)^n =\begin{cases} 1, \ \text{if} \ k \ \text{is even} \\ 0, \ \text{if} \ k \ \text{is even} \end{cases}$$I distinguished two cases, $k$ even and $k$ odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer $n_0$, assume it holds for $n \ge n_0$ with $n$ non negative integer and shows that this assumption implies that it holds for $n+1$; we conclude that the property holds for any $n \ge n_0$.

Is the second "even" meant to be "odd"?

 

[Steven G]

Is the second "even" meant to be "odd"?

What an odd question to ask.
Good catch!

 

[JeffM]

You can bootstrap (starting most easily with even integers). For example,

$$n \text { is any non-negative number} \implies \\ \exists \text { a non-negative integer } m \text { such that } 2m = n.$$
Obviously, it is trivial to justify if n = 0 because then m = 0. Then we have the general case of m = k. It is not hard to show that

$$\sum_{j=0}^{2k} (-1)^{j} = 1 \implies \sum_{j=0}^{2(k+1)} (-1)^{j} = 1.$$
If you can show that, you have proved the even case.

Then it is easy to prove for all odd non-negative numbers.

$$n \text { is an odd non-negative integer} \implies\\ \exists \text { a non-negative integer } m \text { such that } 2m + 1 = n \implies \\ \sum_{j=0}^{2m+1} (-1)^{j} = \left ( \sum_{j=0}^{2m} \right ) + (-1)^{(2m+1)} = 1 - 1 = 0.$$

 

[Ozma]

@Everyone: Thanks for your help, now all is clear. Yes, there is a typo: the second row should be "if k is odd", sorry. If someone would be so gentle to edit that, it will be useful for future readers of this post, thanks.

@JeffM: Yes, I did exactly that, but I was confused about "n+1" in induction. But, as Dr. Peterson said, considering explicitly both cases in terms of m avoid that.

 

[JeffM]

@Everyone: Thanks for your help, now all is clear. Yes, there is a typo: the second row should be "if k is odd", sorry. If someone would be so gentle to edit that, it will be useful for future readers of this post, thanks.

@JeffM: Yes, I did exactly that, but I was confused about "n+1" in induction. But, as Dr. Peterson said, considering explicitly both cases in terms of m avoid that.

Yes, you can prove both the odd and even cases by induction. But sometimes it is simpler to prove one of those cases by induction (usually the even case is less messy) and then prove the other case directly as a result of the first case. Two somewhat different but equally valid methods.

 

[Steven G]

You can bootstrap (starting most easily with even integers). For example,

$$n \text { is any non-negative number} \implies \\ \exists \text { a non-negative integer } m \text { such that } 2m = n.$$
Obviously, it is trivial to justify if n = 0 because then m = 0. Then we have the general case of m = k. It is not hard to show that

$$\sum_{j=0}^{2k} (-1)^{j} = 1 \implies \sum_{j=0}^{2(k+1)} (-1)^{j} = 1.$$
If you can show that, you have proved the even case.

Then it is easy to prove for all odd non-negative numbers.

$$n \text { is an odd non-negative integer} \implies\\ \exists \text { a non-negative integer } m \text { such that } 2m + 1 = n \implies \\ \sum_{j=0}^{2m+1} (-1)^{j} = \left ( \sum_{j=0}^{2m} \right ) + (-1)^{(2m+1)} = 1 - 1 = 0.$$

Very nice!

 

[JeffM]

Very nice!

I see when I defined n that I forgot to stipulate that it was even. No wonder the student did not see what I was trying to show.