In example to get formula for $1^2+2^2+3^2+...+n^2$ they express $f(n)$ as:
$$f(n)=an^3+bn^2+cn+d$$ also known that $f(0)=0$, $f(1)=1$, $f(2)=5$ and $f(3)=14$
Then this values are inserted into function, we get system of equations solve them and get a,b,c,d coefficients and we get that $$f(n)=\frac{n}{6}(2n+1)(n+1)$$
Then it's proven with mathematical induction that it's true for any n.
And question is, why they take 4 coefficients at the beginning, why not $f(n)=an^2+bn+c$ or even more? How they know that 4 will be enough to get correct formula?
Answer
There are several ways to see this:
- As Rasmus pointed one out in a comment, you can estimate the sum by an integral.
- Imagine the numbers being added as cross sections of a quadratic pyramid. Its volume is cubic in its linear dimensions.
- Apply the difference operator $\Delta g(n)=g(n+1)-g(n)$ to $f$ repeatedly. Then apply it to a polynomial and compare the results.
[Edit in response to the comment:]
An integral can be thought of as a limit of a sum. If you sum over $k^2$, you can look at this as adding up the areas of rectangles with width $1$ and height $k^2$, where each rectangle extends from $k-1$ to $k$ in the $x$ direction. (If that's not clear from the words, try drawing it.) Now if you connect the points $(k,k^2)$ by the continuous graph of the function $f(x)=x^2$, the area under that graph is an approximation of the area of the rectangles (and vice versa). So we have
$$1^2+\dotso+n^2\approx\int_0^nk^2\mathrm dk=\frac13n^3\;.$$
No comments:
Post a Comment