2
$\begingroup$

I am trying to figure out this discrete math problem. I am not sure how to do it or even how to really start it. The problem is as follows:

Consider values of $\frac{\sum_{i=1}^n i^2}{\sum_{i=1}^n i}$ for several small values of n. What formula will express $\sum_{i=1}^n i^2$ in terms of $n$. Prove this is a correct formula.

2 Answers 2

2

Let $f(n)=\frac{\sum_{i=1}^ni^2}{\sum_{i=1}^ni}\;.$ Begin by following the instructions: compute $f(n)$ for some small values of $n$.

$\begin{array}{r|cc} n&1&2&3&4&5&6&7\\ \sum_{i=1}^ni^2&1&5&14&30&55&91&140\\ \sum_{i=1}^ni&1&3&6&10&15&21&28\\ f(n)&1&\frac53&\frac73&3&\frac{11}3&\frac{13}3&5 \end{array}$

That last line showing $f(n)$ looks awfully regular. If the pattern isn’t immediately apparent, try putting everything over a denominator of $3$: $\frac33,\frac53,\frac73,\frac93,\frac{11}3,\frac{13}3,\frac{15}3$. Those numerators are clearly $2n+1$, at least as far as this table goes, so we conjecture that $f(n)=\frac{2n+1}3$ for all positive integers $n$.

If this conjecture is correct, $\sum_{i=1}^ni^2=f(n)\sum_{i=1}^ni=\frac13(2n+1)\sum_{i=1}^ni\;.\tag{1}$

I expect that you already know that $\sum_{i=1}^ni=\frac{n(n+1)}2$. (If not, it follows immediately from the formula for the sum of an arithmetic progression.) Combine this with $(1)$ to get a formula for $\sum_{i=1}^ni^2$ that doesn’t involve any summations. Then use mathematical induction to prove that your formula is correct.

1

You are asked to calculate. So let us calculate. Let $f(n)=\frac{\sum_{i=1}^n i^2}{\sum_{i=1}^{n} i}.$ We have $f(1)=\frac{1^2}{1}=1,\quad f(2)=\frac{5}{3},\quad f(3)=\frac{14}{6}=\frac{7}{3},\quad f(4)=\frac{30}{10}=3,\quad f(5)=\frac{11}{3}.$

Maybe make all the denominators equal to $3$. We get $\dfrac{3}{3}$, $\dfrac{5}{3}$, $\dfrac{7}{3}$, $\dfrac{9}{3}$, $\dfrac{11}{3}$. Nice pattern!

We might conjecture on the basis of the evidence so far that $f(n)=\dfrac{2n+1}{3}$. Calculation of the next few terms seems to confirm that.

Now for a proof. Your post hints that you might know a simple formula for $\sum_{i=1}^n i$, and you want a formula for $\sum_{i=1}^n i^2$. There is such a formula, it is $\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}.$ The induction proof is not very complicated.

Remark: Here is a nice way of finding $\sum_{i=1}^n i^2$. Note that $i^3-(i-1)^3=3i^2-3i+1.$ Add up, $i=1$ to $n$. On the left, there is almost total cancellation (telescoping) and we get $n^3$. It follows that $n^3=3\sum_{i=1}^n i^2-3\sum_{i=1}^n i +\sum_{i=1}^n 1.$ Now from the fact that $\sum_{i=1}^n i=\dfrac{n(n+1)}{2}$ and some algebra we get the formula for $\sum_{i=1}^n i^2$.