0
$\begingroup$

I am looking at the induction proof of $$ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} $$

So i do the basis case which holds up.

Then i move on to the induction step and uses k+1 instead of n and starts off like so:

$$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 $$

Then i take out a common factor:

$$ (k+1) (\frac{k(2k+1)}{6} + (k+1)) $$

Then i put it all on the same fraction(is that the right term ?) and get:

$$ (k+1) (\frac{k(2k+1)}{6} + \frac{6(k+1)}{6}) $$

and get

$$ (k+1) + \frac{2k^2+7k+6}{6} $$

My question now is, how does my textbook go from this to the following:

$$ \frac{(k+1)(k+2)(2k+3)}{6} $$

I was thinking about just doing something like, replacing k with 2 then i would get :

$$ \frac{2*2+7*2+6}{6} + \frac{2*2+7*2+6}{6} + \frac{2*2+7*2+6}{6} $$

.

I have a few questions, and i am not that strong in even basic math e.g. i had to look up how to multiply a number with a fraction, so i would really like a answer like i am 5.

  1. Is there any general term, e.g. like i used the "take out the common factor" that i can use here ??
  2. At first i thouth i would arrive at a solution that looked like $$ \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} $$ And it kind of does, but if i had to do this by my self i wouldn't be able to know that i had arrived at the end result, what is it exactly that the result should look like? i was thinking about that the solution should basically just be the initial statement but with n+1 instead of n, can someone explain that in a more formal manner? because its hard to solve this if you are not even sure what you are looking for.
  3. A more general question, that is probably way over this scope, there is a lot of factorizing in this, is there any good resources that looks at a lot of induction proofs like the person doesn't have a solid background in math? or would it help to just go back into college/high school math and read up on the fundamentals of equations?
$\endgroup$
  • $\begingroup$ insert the assumption in the last step, its like that 99% of all proofs by induction. do you understand that? and also do what simple art says. $\endgroup$ – SAJW Oct 23 '16 at 13:54
  • $\begingroup$ Now i don't quite understand how to insert the assumption. So you are saying that i should use the original statement here somehow? $\endgroup$ – DenLilleMand Oct 23 '16 at 14:00
0
$\begingroup$

See that:

$$\begin{align}(k+1)\left( \frac{k(2k+1)}{6} + (k+1)\right)&=(k+1)\left( \frac{k(2k+1)}{6} + \frac{6(k+1)}6\right)\\&=(k+1)\left( \frac{2k^2+k}{6} + \frac{6k+6}6\right)\\&=(k+1)\left( \frac{2k^2+k+6k+6}{6}\right)\\&=(k+1)\left( \frac{2k^2+7k+6}{6}\right)\\&=(k+1)\left( \frac{(k+2)(2k+3)}{6}\right)\\&=\frac{(k+1)(k+2)(2k+3)}6\end{align}$$

If your having difficulty with the factoring step, I would review how to factor quadratics.

$\endgroup$
  • $\begingroup$ The fastest trick to spotting factors here might be to use the rational roots theorem. $\endgroup$ – Simply Beautiful Art Oct 23 '16 at 14:24
  • $\begingroup$ This was exactly what i was looking for, thank you ! ... i hate when books take it for granted. Do you know of any resource that teaches discrete math & basic algebra altogether? or am i doomed to go back to read a whole book about algebra(even though thats a good idea too)? $\endgroup$ – DenLilleMand Oct 23 '16 at 14:34
  • $\begingroup$ @DenLilleMand Just review the factoring quadratics section? $\endgroup$ – Simply Beautiful Art Oct 23 '16 at 14:36
  • $\begingroup$ okay :) thanks! $\endgroup$ – DenLilleMand Oct 23 '16 at 14:36
0
$\begingroup$

You forgot a pair of parentheses on factoring $k+1$. You should have written $$(k+1)\biggl( \frac{k(2k+1)}{6} + (k+1)\biggr).$$

$\endgroup$
  • $\begingroup$ okay i did that now, thanks. $\endgroup$ – DenLilleMand Oct 23 '16 at 13:58
0
$\begingroup$

Not entirely sure on what question 1 is about, but I believe the answer is $n=1$. This is the simplest and the start of the induction.

For question 2, see that if we know our formula works for $n=1$, we have proven that it works for $n+1$.

In this case, $n+1=2$, so our formula works for $n=2$ now. But we also proved it works for $n+1$, which then becomes a proof for $n=3$. etc. we have proved it for $n=1,2,3,4,\dots$


Induction is not a process that solves the problem, rather it shows that some solution is indeed the solution. The general steps are to show it is true for $n=1$, then for all $n\implies n+1$, the proof follows true for $n=1,2,3,\dots$

$\endgroup$
  • $\begingroup$ Yeah okay, i understand that if i prove n+1 i prove everything. Its more the process of going from n to n+1 and then back to a statement that we regard as a proof i am having issues with. $\endgroup$ – DenLilleMand Oct 23 '16 at 14:04
  • $\begingroup$ @DenLilleMand Let $f(n)$ be the solution for some $n$. Prove that if $\sum_{p=1}^np^2=f(n)$, then we have $\sum_{p=1}^{n+1}p^2=f(n+1)$. Then show it works for $n=1$. Then done. Unless you are having trouble with the algebra, whereupon I'm not sure how well I can help you there. $\endgroup$ – Simply Beautiful Art Oct 23 '16 at 14:07
  • $\begingroup$ There is no doubt that i have to read up on my algebra. This is actually more of a algebra question than it is induction, now that i think about it. That was also what question 1 was directed at, if there is a smart algebra way of getting from one from to another. $\endgroup$ – DenLilleMand Oct 23 '16 at 14:23

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.