Friday, January 18, 2019

summation - Proving $sum_{i=1}^ni^2=frac{n(n+1)(2n+1)}{6}$ with Induction





I've been watching countless tutorials but still can't quite understand how to prove something like the following:
$$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$$



original image




The ^2 is throwing me off, I really wish I can show you what I've already tried but I have absolutely no clue where to start. I've also looked around for similar problems but can't find any that start with ^2.



I appreciate all help whatsoever, thank you!


Answer



Tips:



Every proof by induction contains the following steps: a base case, and the inductive step. Almost always, you should start with the base case first. For a base case, try to find the simplest case that works for whatever equality or thing you're trying to show. For example, if you're trying to show



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




I would try the case where $n=1$ first. Just show that it works when you plug in $n=1$ on both sides.



The next step is the trickier one, but it can be very algorithmic if you learn how to do it. First, what you do is assume that whatever you're trying to prove is true for some $n=k$. This assumption is called "the inductive hypothesis." Then you have to do something to show that if your statement is true when $n=k$, then it is also true when $n=k+1$. All of this constitutes "the inductive step." Once you do that you're done; you can simply say "Therefore by PMI, < some theorem > is true for all $n\ge$ < your base case >."



When dealing with equations like the one in your question, I will outline simpler approach. Once you assume your inductive hypothesis, rewrite your equation with $n=k$, and depending on the situation, perform some operation to include $k+1$ on both sides of the equation. In this case, we are adding successive squares, so we add $(k+1)^2$ to both sides. Suppose,



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



is true for $n=k$. Then




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



Now we can add $(k+1)^2$ to both sides



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



Now you need to manipulate the r.h.s. to look like $\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$. Once you're done you can write the conclusion. Can you do the rest?


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...