Question about induction when considering odd and even cases

O

Ozma

Junior Member
Joined
Oct 14, 2020
Messages
78
I was trying to prove by induction that
[math]\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[/math]I distinguished two cases, [imath]k[/imath] even and [imath]k[/imath] odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer [imath]n_0[/imath], assume it holds for [imath]n \ge n_0[/imath] with [imath]n[/imath] non negative integer and shows that this assumption implies that it holds for [imath]n+1[/imath]; we conclude that the property holds for any [imath]n \ge n_0[/imath].

However, if I assume [imath]k[/imath] even, it works for [imath]k=0[/imath] but when I have to prove that it works for [imath]k+1[/imath] I get that, since [imath]k[/imath] is even, is odd and hence I can't prove that this holds for all even [imath]k[/imath] 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 [imath]k_0[/imath], assume it holds for a generic even [imath]k[/imath] and show that this implies it holds for the next even number [imath]k+2[/imath]. 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 [imath]n[/imath] with [imath]n+1[/imath]? I thought that I can write an even number [imath]k=2m[/imath] with [imath]m[/imath] non negative integer and use "classical" induction with [imath]m+1[/imath], but I should work on [imath]k[/imath] and not on [imath]m[/imath]. What is happening here?
 
Why not just use [imath]k\mod 2~~?[/imath]
Or look HERE
 
Last edited:
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
 
Ozma said:
I was trying to prove by induction that
[math]\sum_{n=0}^k (-1)^n =\begin{cases} 1, \ \text{if} \ k \ \text{is even} \\ 0, \ \text{if} \ k \ \text{is even} \end{cases}[/math]I distinguished two cases, [imath]k[/imath] even and [imath]k[/imath] odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer [imath]n_0[/imath], assume it holds for [imath]n \ge n_0[/imath] with [imath]n[/imath] non negative integer and shows that this assumption implies that it holds for [imath]n+1[/imath]; we conclude that the property holds for any [imath]n \ge n_0[/imath].

However, if I assume [imath]k[/imath] even, it works for [imath]k=0[/imath] but when I have to prove that it works for [imath]k+1[/imath] I get that, since [imath]k[/imath] is even, is odd and hence I can't prove that this holds for all even [imath]k[/imath] 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 [imath]k_0[/imath], assume it holds for a generic even [imath]k[/imath] and show that this implies it holds for the next even number [imath]k+2[/imath]. 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 [imath]n[/imath] with [imath]n+1[/imath]? I thought that I can write an even number [imath]k=2m[/imath] with [imath]m[/imath] non negative integer and use "classical" induction with [imath]m+1[/imath], but I should work on [imath]k[/imath] and not on [imath]m[/imath]. What is happening here?
Click to expand...
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.
 
Ozma said:
I was trying to prove by induction that
[math]\sum_{n=0}^k (-1)^n =\begin{cases} 1, \ \text{if} \ k \ \text{is even} \\ 0, \ \text{if} \ k \ \text{is even} \end{cases}[/math]I distinguished two cases, [imath]k[/imath] even and [imath]k[/imath] odd. Now I had a doubt: in induction, we prove that a property holds for a certain non negative integer [imath]n_0[/imath], assume it holds for [imath]n \ge n_0[/imath] with [imath]n[/imath] non negative integer and shows that this assumption implies that it holds for [imath]n+1[/imath]; we conclude that the property holds for any [imath]n \ge n_0[/imath].
Click to expand...
Is the second "even" meant to be "odd"?
 
You can bootstrap (starting most easily with even integers). For example,

[math]n \text { is any non-negative number} \implies \\ \exists \text { a non-negative integer } m \text { such that } 2m = n.[/math]
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

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

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

[math]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.[/math]
 
@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.
 
Ozma said:
@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.
Click to expand...
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.
 
JeffM said:
You can bootstrap (starting most easily with even integers). For example,

[math]n \text { is any non-negative number} \implies \\ \exists \text { a non-negative integer } m \text { such that } 2m = n.[/math]
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

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

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

[math]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.[/math]
Click to expand...
Very nice!
 
You must log in or register to reply here.
Top