My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   I need to understand and help for a proof (http://mymathforum.com/number-theory/342691-i-need-understand-help-proof.html)

 David Roy November 6th, 2017 10:56 AM

I need to understand and help for a proof

Find a closed formula for the sum f(n) = 1^4 + 2^4 + 3^4 + . . . + n^4

 Maschke November 6th, 2017 11:04 AM

http://mathforum.org/library/drmath/view/56935.html

 skipjack November 7th, 2017 12:06 AM

The formula is n(n + 1)(2n + 1)(3n² + 3n - 1)/30, which can be proved by mathematical induction.

 Country Boy December 1st, 2017 03:42 AM

You can derive that formula using "Newton's divided difference formula":
Setting $\displaystyle f(n)= 1+ 2^4+ 3^4+ \cdot\cdot\cdot+ n^4$
with f(0)= 0, f(1)= 1, f(2)= 17, f(3)= 98, f(4)= 354, f(5)= 989, f(6)= 2275.

The "first differences" are
$\displaystyle \Delta f(0)= f(1)- f(0)= 1$
$\displaystyle \Delta f(1)= f(2)- f(1)= 16$
$\displaystyle \Delta f(2)= f(3)- f(2)= 81$
$\displaystyle \Delta f(3)= f(4)- f(3)= 256$
$\displaystyle \Delta f(4)= f(5)- f(4)= 625$
$\displaystyle \Delta f(5)= f(6)- f(5)= 1296$
(Those are, of course, the fourth powers.)

The "second differences" are
$\displaystyle \Delta^2 f(0)= 16- 1= 15$
$\displaystyle \Delta^2 f(1)= 81- 16= 65$
$\displaystyle \Delta^2 f(2)= 256- 81= 175$
$\displaystyle \Delta^2 f(3)= 625- 256= 369$
$\displaystyle \Delta^2 f(4)= 1296- 625= 671$

The "third differences" are
$\displaystyle \Delta^3 f(0)= 65- 15= 50$
$\displaystyle \Delta^3 f(1)= 175- 65= 110$
$\displaystyle \Delta^3 f(2)= 369- 175= 194$
$\displaystyle \Delta^3 f(3)= 671- 369= 302$

The "fourth differences" are
$\displaystyle \Delta^4(0)= 110- 50= 60$
$\displaystyle \Delta^4(1)= 194- 110= 84$
$\displaystyle \Delta^4(2)= 302- 194= 108$

The "fifth differences" are
$\displaystyle \Delta^5(0)= 84- 60= 24$
$\displaystyle \Delta^5(1)= 108- 84= 24$

The "fifth differences" are all the same (which you can verify by extending the x-values larger than 6 and calculating further differences) so all succeeding differences are 0.

"Newton's divided difference method" says that $\displaystyle f(x)= f(0)+ \Delta f(0)x- \frac{\Delta^2 f(0)}{2}x(x- 1)+ \frac{\Delta^3 f(0)}{3!}x(x- 1)(x- 2)+ \cdot\cdot\cdot$. Note the similarities to (and differences from) Taylor's series.

Here, that gives $\displaystyle f(x)= 0+ x+ \frac{15}{2}x(x- 1)+ \frac{50}{6}x(x- 1)(x- 2)+ \frac{60}{24}x(x- 1)(x- 2)(x- 3)+ \frac{24}{120}x(x- 1)(x- 2)(x- 3)(x- 4)$

 Country Boy December 1st, 2017 06:24 AM

Yet another way: knowing, perhaps from "divided differences" as above, that the sum, to n, of kth powers is a k+ 1 degree polynomial, we can write this as fifth degree polynomial in n: an^5+ bn^4+ cn^3+ dn^2+ en+ f.

Taking n= 0, f= 0.
Taking n= 1, a+ b+ c+ d+ e+ f= a+ b+ c+ d+ e= 1.
Taking n= 2. 32a+ 16b+ 8c+ 4d+ 2e= 17.
Taking n= 3, 242a+ 81b+ 27c+ 9d+ 3e= 98.
Taking n= 4, 1024a+ 256b+ 64c+ 16d+ 4e= 354.
Taking n= 5, 3125a+ 625b+ 125c+ 25d+ 5e= 989.

That is 6 linear equations to solve for a, b, c, d, e, and f.

 v8archie December 1st, 2017 07:52 AM

\begin{align*}
n-(n-1) &= 1 \\
\sum_{k=1}^n \big( k - (k-1) \big) &= \sum_{k=1}^n 1 \\
\big(n - \cancel{(n-1)}\big) + \big(\cancel{(n-1)} - \cancel{(n-2)}\big) + \ldots + \big(\cancel{2} - \cancel{1}\big) + \big(\cancel{1} - 0\big) &= \sum_{k=1}^n 1 \\
\sum_{k=1}^n 1 &= n \\[8pt]
\hline
n^2-(n-1)^2 &= n^2 - (n^2 - 2n + 1) = 2n-1 \\
\sum_{k=1}^n \big( k^2 - (k-1)^2 \big) &= \sum_{k=1}^n (2k-1) \\
\big(n^2 - \cancel{(n-1)^2}\big) + \big(\cancel{(n-1)^2} - \cancel{(n-2)^2}\big) + \ldots + \big(\cancel{2^2} - \cancel{1^2}\big) + \big(\cancel{1^2} - 0\big) &= \sum_{k=1}^n 2k - \sum_{k=1}^n 1 \\
n^2 &= 2\sum_{k=1}^n k - \sum_{k=1}^n 1 \\
\sum_{k=1}^n k &= \frac12 \left(n^2 + \sum_{k=1}^n 1\right) \\ &= \frac12\left(n^2 + n\right) = \frac12n(n+1) \\[8pt]
\hline
n^3-(n-1)^3 &= n^3 - (n^3 - 3n^2 + 3n - 1) = 3n^2 - 3n + 1 \\
\sum_{k=1}^n \big( k^3 - (k-1)^3 \big) &= \sum_{k=1}^n (3k^2 - 3k + 1) \\
\big(n^3 - \cancel{(n-1)^3}\big) + \big(\cancel{(n-1)^3} - \cancel{(n-2)^3}\big) + \ldots + \big(\cancel{2^3} - \cancel{1^3}\big) + \big(\cancel{1^3} - 0^3\big) &= \sum_{k=1}^n 3n^2 - \sum_{k=1}^n 3n + \sum_{k=1}^n 1 \\
n^3 &= 3\sum_{k=1}^n k^2 - 3\sum_{k=1}^n k + \sum_{k=1}^n 1 \\
\sum_{k=1}^n k^2 &= \frac13 \left(n^3 + 3\sum_{k=1}^n k - \sum_{k=1}^n 1\right) \\ &= \frac12\left(n^3 + \frac32n(n+1) - n\right) = \frac16n(2n+1)(n+1) \\[8pt]
\hline
& \vdots
\end{align*}
etc.

 jks December 9th, 2017 07:08 PM

I think that I have another way of determining the coefficients using the differentials as given in post #4. It involves two (possible) properties of Pascal's Triangle (PT).

I will start with $n=1$, with the inverted triangle below (row 0 is just the terms):

$\displaystyle \large {\begin{array}{c c} & n & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 \\ row \\ 0 & & 1 & & 17 & & 98 & & 354 & & 979 & & 2275 & & 4676 \\ 1 & & & 16 & & 81 & & 256 & & 625 & & 1296 & & 2401 \\ 2 & & & & 65 & & 175 & & 369 & & 671 & & 1105 \\ 3 & & & & & 110 & & 195 & & 302 & & 434 \\ 4 & & & & & & 84 & & 108 & & 132 \\ 5 & & & & & & & 24 & & 24 \end{array}}$

As stated in earlier posts, the number of subtractions to get to a constant is 5, so it is a fifth order polynomial that we are looking for, $a \cdot n^5+b \cdot n^4+c \cdot n^3+d \cdot n^2+e \cdot n+f$.

----------------------

To get $a$:

The constant is 24 so divide by 5!=120

$\displaystyle a=\large \frac{24}{5!}= \frac{1}{5}$

The factorial is the number of subtractions needed to get to the constant.

Now that we have $a$, we could subtract off $a \cdot n^5$ from each term and do another triangle until we get a constant and divide the constant by 4!. But instead let's use the triangle that we already have.

----------------------

To get $b$:

First calculate the following sum using the value for $a$:

$\displaystyle \large s = \frac{1}{5} \left (1 \cdot 5^5 - 4 \cdot 4^5 + 6 \cdot 3^5 - 4 \cdot 2^5 + 1 \cdot 1^5 \right)=72$

Then:

$\displaystyle \large b=\frac{84-72}{4!}=\frac{12}{24}=\frac{1}{2}$

with the value of 84 coming from the first term in row 4 of the inverted triangle above. The power of the numbers 5 down to 1 is 5 (since it is $a \cdot n^5$), and the coefficients come from the fourth row of PT, starting with a + and then alternating signs.

----------------------

To get $c$:

First calculate the following sum using the values for $a$ and $b$:

$\displaystyle \large s = \frac{1}{5} \left (1 \cdot 4^5 - 3 \cdot 3^5 + 3 \cdot 2^5 - 1 \cdot 1^5 \right) + \frac{1}{2} \left (1 \cdot 4^4 - 3 \cdot 3^4 + 3 \cdot 2^4 - 1 \cdot 1^4 \right) = 108$

Then:
$\displaystyle \large c=\frac{110-108}{3!}=\frac{2}{6}=\frac{1}{3}$

Notice that the coefficients are for row 3 of PT.

----------------------

To get $d$:

First calculate the following sum using the values for $a$, $b$, and $c$:

$\displaystyle \large s = \frac{1}{5} \left (1 \cdot 3^5 - 2 \cdot 2^5 + 1 \cdot 1^5 \right) + \frac{1}{2} \left (1 \cdot 3^4 - 2 \cdot 2^4 + 1 \cdot 1^4 \right) + \frac{1}{3} \left (1 \cdot 3^3 - 2 \cdot 2^3 + 1 \cdot 1^3 \right)= 65$

Then:
$\displaystyle \large d=\frac{65-65}{2!}=0$

----------------------

To get $e$:

First calculate the following sum using the values for $a$, $b$, $c$, and $d$:

$\displaystyle \large s = \frac{1}{5} \left (1 \cdot 2^5 - 1 \cdot 1^5 \right) + \frac{1}{2} \left (1 \cdot 2^4 - 1 \cdot 1^4 \right) + \frac{1}{3} \left (1 \cdot 2^3 - 1 \cdot 1^3 \right )+ 0 \cdot \left (1 \cdot 2^2 - 1 \cdot 1^2 \right)= 16 \frac{1}{30}$

Then:
$\displaystyle \large e=\frac{16-16 \frac{1}{30}}{1!}=-\frac{1}{30}$

----------------------

To get f:

$\displaystyle \large 1=\frac{1}{5}+\frac{1}{2}+\frac{1}{3}-\frac{1}{30}+f$

$\displaystyle \large f=0$

----------------------

So the polynomial is:

$\displaystyle \large \frac{1}{5} \cdot n^5 + \frac{1}{2} \cdot n^4 + \frac{1}{3} \cdot n^3 - \frac{1}{30} \cdot n$

Has anyone seen this method? I will post a new thread try to explain it.

 All times are GMT -8. The time now is 09:02 AM.