a problem solving with induction
- Thread starter lupinz
- Start date
I have trouble reading your writing.
[MATH]\text {Prove } P_n: \ \sum_{j=1}^{2n} j^2 = \frac{n}{3} * (2n + 1)(4n + 1) \text { for any integer } n \ge 1.[/MATH]
[MATH]n = 1 \implies \sum_{j=1}^{2n} j^2 = 1 + 2^2 = 5 = \frac{1}{3} * 3 * 5 = \frac{n}{3} * (2n + 1)(4n + 1).[/MATH]
[MATH]\therefore \exists \text { at least one integer} \ge 1 \text { such that } P_n \text { is true.}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary integer such that } P_k \text { is true.}[/MATH]
[MATH]\therefore k \ge 1 \text { and } \sum_{j=1}^{2k} j^2 = \frac{k}{3} * (2k + 1)(4k + 1).[/MATH]
[MATH]\sum_{j=1}^{2(k+1)} j^2 = \sum_{j=1}^{2k+2} j^2 = (2k + 1)^2 + (2k + 2)^2 + \sum_{j=1}^{2k} j^2 =[/MATH]
[MATH]4k^2 + 4k + 1 + 4k^2 + 8k + 4 + \frac{k}{3} * (2k + 1)(4k + 1) = 8k^2 + 12k + 5 + \dfrac{k(8k^2 + 6k + 1)}{3} =[/MATH]
[MATH]\dfrac{24k^2 + 36k + 15 + 8k^3 + 6k^2 + k}{3} = \dfrac{8k^3 + 30k^2 + 37k + 15}{3} = \dfrac{8k^3 + 8k^2 + 22k^2 + 22k + 15k + 15}{3} =[/MATH]
[MATH]\dfrac{8k^2(k + 1) + 22k(k + 1) + 15(k + 1)}{3} = \frac{k + 1}{3} * (8k^2 + 22k + 15) =[/MATH]
[MATH]\frac{k + 1}{3} * (2k + 3)(4k + 5) = \frac{k + 1}{3} * (2k + 2 + 1)(4k + 4 + 1) = \frac{k+1}{3} * \{2(k + 1) + 1\}\{4(k+1) + 1\} \text { Q.E.D.}[/MATH]
Because I cannot read your writing, I do not know where you went wrong.
[MATH]\text {Prove } P_n: \ \sum_{j=1}^{2n} j^2 = \frac{n}{3} * (2n + 1)(4n + 1) \text { for any integer } n \ge 1.[/MATH]
[MATH]n = 1 \implies \sum_{j=1}^{2n} j^2 = 1 + 2^2 = 5 = \frac{1}{3} * 3 * 5 = \frac{n}{3} * (2n + 1)(4n + 1).[/MATH]
[MATH]\therefore \exists \text { at least one integer} \ge 1 \text { such that } P_n \text { is true.}[/MATH]
[MATH]\text {Let } k \text { be an arbitrary integer such that } P_k \text { is true.}[/MATH]
[MATH]\therefore k \ge 1 \text { and } \sum_{j=1}^{2k} j^2 = \frac{k}{3} * (2k + 1)(4k + 1).[/MATH]
[MATH]\sum_{j=1}^{2(k+1)} j^2 = \sum_{j=1}^{2k+2} j^2 = (2k + 1)^2 + (2k + 2)^2 + \sum_{j=1}^{2k} j^2 =[/MATH]
[MATH]4k^2 + 4k + 1 + 4k^2 + 8k + 4 + \frac{k}{3} * (2k + 1)(4k + 1) = 8k^2 + 12k + 5 + \dfrac{k(8k^2 + 6k + 1)}{3} =[/MATH]
[MATH]\dfrac{24k^2 + 36k + 15 + 8k^3 + 6k^2 + k}{3} = \dfrac{8k^3 + 30k^2 + 37k + 15}{3} = \dfrac{8k^3 + 8k^2 + 22k^2 + 22k + 15k + 15}{3} =[/MATH]
[MATH]\dfrac{8k^2(k + 1) + 22k(k + 1) + 15(k + 1)}{3} = \frac{k + 1}{3} * (8k^2 + 22k + 15) =[/MATH]
[MATH]\frac{k + 1}{3} * (2k + 3)(4k + 5) = \frac{k + 1}{3} * (2k + 2 + 1)(4k + 4 + 1) = \frac{k+1}{3} * \{2(k + 1) + 1\}\{4(k+1) + 1\} \text { Q.E.D.}[/MATH]
Because I cannot read your writing, I do not know where you went wrong.
Or prove by induction, the standard formula:
[MATH]\sum_{k=1}^{n} k^2 = \frac{n}{6} (n + 1)(2n + 1) \hspace5ex n \in \mathbb{Z}^+[/MATH](This formula is standard and can be looked up or taken from the question by replacing [MATH]2n[/MATH] with [MATH]n[/MATH]).
The inductive proof is less messy than the current one.
Then finally, substitute [MATH]2n[/MATH] for [MATH]n[/MATH] and you have your formula.
[MATH]\sum_{k=1}^{n} k^2 = \frac{n}{6} (n + 1)(2n + 1) \hspace5ex n \in \mathbb{Z}^+[/MATH](This formula is standard and can be looked up or taken from the question by replacing [MATH]2n[/MATH] with [MATH]n[/MATH]).
The inductive proof is less messy than the current one.
Then finally, substitute [MATH]2n[/MATH] for [MATH]n[/MATH] and you have your formula.
As you know, there is nothing wrong with what you did (as always)! This is just an alternative.
An elegant alternative.
I will say, however, that I think the original poster might learn more from the ugly, brute-force approach. I am still not sure where he went astray. But restating the problem to rely on a simpler solution may not help him see on his own where he went astray. But I truly am charmed by your solution by re-statement.
Cubist
Senior Member
- Joined
- Oct 29, 2019
- Messages
- 1,686
hey,
I'm trying to solve prove an equation with induction for every natural n (n>0)
but it just doesn't add up.
I must be missing something...
would really appreciate the help!
and sorry it looks bad
Looking at your work, it seems that you made the mistake of putting n=k+1 into the WHOLE equation (both LHS and RHS) in one go. This doesn't prove anything. You have to put n=k+1 into ONE SIDE of the equation and then manipulate it using algebra, and also using the result of the equation when n=k, in order to make it look like the OTHER SIDE (with n=k+1). See post#3, where @JeffM puts n=k+1 into the LHS only. This is then manipulated so that it looks like the RHS when n=k+1. This proves that if the equation is true for k then it is also true for k+1.
Last edited:
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,561
There are many problems out there to get your hands dirty with. I think that the cleanest way of doing a problem is the best way. Lex's method, I feel, is the correct way.
Having said that, since the OP had trouble with the algebra in his work, then he must figure out where his mistake is. This is how you learn algebra
Having said that, since the OP had trouble with the algebra in his work, then he must figure out where his mistake is. This is how you learn algebra
@lupinz
I know this is a bit late, but having looked at your work, the only mistake you made was:
when [MATH]n=k \text{, the sum is }1^2 + 2^2 + 3^2 +...+(2k)^2[/MATH]when [MATH]n=k+1 \text{ the sum is } 1^2 + 2^2 + 3^2 +...+(2k)^2 + (2k+1)^2 + (2k+2)^2[/MATH]when n goes up by 1, there are actually 2 extra terms. You only added [MATH](2k+2)^2[/MATH].
So this line:
should have [MATH]+ (2k+1)^2[/MATH] inserted on the left hand side. Then your work is correct. (Although there are obviously problems with the layout).
I know this is a bit late, but having looked at your work, the only mistake you made was:
when [MATH]n=k \text{, the sum is }1^2 + 2^2 + 3^2 +...+(2k)^2[/MATH]when [MATH]n=k+1 \text{ the sum is } 1^2 + 2^2 + 3^2 +...+(2k)^2 + (2k+1)^2 + (2k+2)^2[/MATH]when n goes up by 1, there are actually 2 extra terms. You only added [MATH](2k+2)^2[/MATH].
So this line:
should have [MATH]+ (2k+1)^2[/MATH] inserted on the left hand side. Then your work is correct. (Although there are obviously problems with the layout).
@Jomo
I disagree in part with your statement that “cleanest is best.”
Certainly, if you as a teacher are trying to convey the reasoning behind an obscure answer, the simplest reasoning will be clear to the greatest number of students. That is the context where I FULLY agree that cleanest is always best.
However, to identify the cleanest reasoning often requires knowledge or insight or both that a student may lack. The constant presentation of “clean“ demonstrations in all cases can make the student say “Oh, I never would have seen that. I am no good at math.” The fact is that there frequently are multiple ways to reach a result and that the one that is easiest to find is not the cleanest to do. In other words, the esthetic way is not always the obvious way.
This problem is I think an example. The obvious solution is to just do the induction in the normal way, which requires only realizing that two terms are added to the series and then avoiding errors in the resulting algebra. It is prone to algebraic error (I made one myself my first go round) and is not esthetically pleasing. But it requires no flash of insight or ancillary knowledge. If the student does not recall the formula for the sum of successive squares or if the student does not think of a change in variable, then Lex’s lovely method is out of reach. I think it is very important that students learn that just plugging away frequently works.
Moreover, sometimes you learn something from the brute-force method that cannot be taught by an elegant method. I doubt this student will ever again be careless in thinking about the number of terms in a series.
I disagree in part with your statement that “cleanest is best.”
Certainly, if you as a teacher are trying to convey the reasoning behind an obscure answer, the simplest reasoning will be clear to the greatest number of students. That is the context where I FULLY agree that cleanest is always best.
However, to identify the cleanest reasoning often requires knowledge or insight or both that a student may lack. The constant presentation of “clean“ demonstrations in all cases can make the student say “Oh, I never would have seen that. I am no good at math.” The fact is that there frequently are multiple ways to reach a result and that the one that is easiest to find is not the cleanest to do. In other words, the esthetic way is not always the obvious way.
This problem is I think an example. The obvious solution is to just do the induction in the normal way, which requires only realizing that two terms are added to the series and then avoiding errors in the resulting algebra. It is prone to algebraic error (I made one myself my first go round) and is not esthetically pleasing. But it requires no flash of insight or ancillary knowledge. If the student does not recall the formula for the sum of successive squares or if the student does not think of a change in variable, then Lex’s lovely method is out of reach. I think it is very important that students learn that just plugging away frequently works.
Moreover, sometimes you learn something from the brute-force method that cannot be taught by an elegant method. I doubt this student will ever again be careless in thinking about the number of terms in a series.
Yes. I remember you asked about that before. There's definitely something strange going on.
Ah. That explains it. I had forgotten about that delay at the start.