# How can i solve a complex induction exercise? (formula for sum of fourth powers)

I have an induction exercise:

It is $n \in \mathbb{N_0}$. Show:

$$\sum\limits_{k=1}^{n} k^4 = \frac 1 {30} n(n+1)(2n+1)(3n^2+3n-1)$$

As far as is understand it, you have to put in $(n+1)^4$ at the end and you have to resolve it to the old function replacing $n$ with $n+1$. So i have on my paper.

$$\frac 1 {30} (n+1)((n+1)+1)(2(n+1)+1)(3(n+1)^2+3(n+1)-1) = \frac 1 {30} n(n+1)(2n+1)(3n^2+3n-1) + (n+1)^4$$

How can i solve this exercise, i probably have to disprove it because it is not true for numbers $> 1$? All the other examples were with very tiny formulas.

I really tried to find a solution, what should i do?

-
If you can show that that equality holds, then you have the key step in the proof. – Alex Becker Jan 11 '12 at 22:46
Why do you say it is not true for $n > 1$? When $n = 2$, for example, we have $$\sum_{k=1}^2 k^4 = 1^4 + 2^4 = 17 = \frac{1}{30}2(3)(5)(12 + 6 -1),$$ which is true. To prove this in general, you show that the formula holds for $n = 1$, and then show that if the formula holds for $m = n$, then it also holds for $m = n+1$. In this way, you can show that it holds for all natural numbers $n$. – JavaMan Jan 11 '12 at 22:47
You are right, i made a mistake. Thanks for your answer. – tonlap Jan 11 '12 at 23:40

There is one way to more or less predict the coefficients in one of these sums. It is not a use of induction as such, but I think it is worth knowing when you are beginning the study of induction. It is just Pascal's triangle. $$\sum_{k=0}^n \left( \begin{array}{c} k \\ 0 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 1 \end{array} \right),$$ $$\sum_{k=1}^n \left( \begin{array}{c} k \\ 1 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 2 \end{array} \right),$$ $$\sum_{k=2}^n \left( \begin{array}{c} k \\ 2 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 3 \end{array} \right),$$ $$\sum_{k=3}^n \left( \begin{array}{c} k \\ 3 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 4 \end{array} \right),$$ $$\sum_{k=4}^n \left( \begin{array}{c} k \\ 4 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 5 \end{array} \right).$$

So then you need expressions such as $$k = \left( \begin{array}{c} k \\ 1 \end{array} \right),$$ $$k^2 = 2 \; \left( \begin{array}{c} k \\ 2 \end{array} \right) + \left( \begin{array}{c} k \\ 1 \end{array} \right),$$ $$k^3 = 6 \; \left( \begin{array}{c} k \\ 3 \end{array} \right) + 6 \; \left( \begin{array}{c} k \\ 2 \end{array} \right) + \left( \begin{array}{c} k \\ 1 \end{array} \right),$$ $$k^4 = 24 \; \left( \begin{array}{c} k \\ 4 \end{array} \right) + 36 \; \left( \begin{array}{c} k \\ 3 \end{array} \right) + 14 \; \left( \begin{array}{c} k \\ 2 \end{array} \right) + \left( \begin{array}{c} k \\ 1 \end{array} \right),$$ $$k^5 = 120 \; \left( \begin{array}{c} k \\ 5 \end{array} \right) + 240 \; \left( \begin{array}{c} k \\ 4 \end{array} \right) + 150 \; \left( \begin{array}{c} k \\ 3 \end{array} \right) + 30 \; \left( \begin{array}{c} k \\ 2 \end{array} \right) + \left( \begin{array}{c} k \\ 1 \end{array} \right).$$ It helps that these expressions still work if you take $$\left( \begin{array}{c} k \\ t \end{array} \right)= \; 0$$ whenever $0 \leq k < t.$ Indeed, under the same rule, the sums in the first section can all start at $k=0$ instead of the beginning values I typed in.

Well, just for laughs, I worked it through, $$\sum_{k=0}^n k^4 = 24 \; \left( \begin{array}{c} n+1 \\ 5 \end{array} \right) + 36 \; \left( \begin{array}{c} n+1 \\ 4 \end{array} \right) + 14 \; \left( \begin{array}{c} n+1 \\ 3 \end{array} \right) + \left( \begin{array}{c} n+1 \\ 2 \end{array} \right).$$ Writing things out, I got a common denominator of 30, then I put everything together into one fraction and got $$\sum_{k=0}^n k^4 = \frac{6 n^5 + 15 n^4 + 10 n^3 -n}{30},$$ where the lack of a constant term was predictable but the lack of an $n^2$ term seems an accident.

Now that I have been through this one, line by line, I can see how absolutely crucial it is that I be able to correctly rewrite one of the formulas in the first section as starting at $k=0,$ as
$$\sum_{k=0}^n \left( \begin{array}{c} k \\ 4 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 5 \end{array} \right),$$ which is true because we take $$\left( \begin{array}{c} k \\ t \end{array} \right)= \; 0$$ whenever $0 \leq k < t.$

-
Thank you, this was very helpful. – tonlap Jan 16 '12 at 19:47

HINT $\$ Prove by induction $\rm\displaystyle\ f(n)\: = \sum_{\ \: k\ =\ 1_{\phantom .}}^n\ g(k)\ \iff\ f(n) - f(n-1)\ =\ g(n),\ \ f(1) = g(1)$
Then your exercise reduces to verifying the RHS equations (a rote polynomial computation).

For many further examples see my prior posts on telescopy.

-
Thanks, i never thought of this that way. – tonlap Jan 11 '12 at 23:26

$\displaystyle \sum_{k=1}^{n+1}k^{4}=\sum_{k=1}^{n}k^4+(n+1)^{4}$

First show that it holds for $n=1$. Then assume the formula holds for some $n \in \mathbb{N}$. Once you do that, you can insert the formula on the right hand side. Showing that the expression on the right hand side reduces to the original formula (which you started to do) with $n$ replaced by $n+1$ will complete the proof.

-

by induction we show that: $$1+2^4+3^4+....+n^4 =\frac 1 {5}n^5+\frac 1 {2}n^4+\frac 1 {3}n^3-\frac 1 {30}n$$

for $n=1$ $$1=\frac 1 {30}\cdot2\cdot3\cdot5=1$$

now suppose that is true for $n$, and show that and show that it is also true for $n+1$, that is

$$1+2^4+3^4+....+n^4+(n+1)^4 =\frac 1 {5}(n+1)^5+\frac 1 {2}(n+1)^4+\frac 1 {3}(n+1)^3-\frac 1 {30}(n+1)$$ this equality is verified if the following equality is verified

$$\frac 1 {5}(n+1)^5+\frac 1 {2}(n+1)^4+\frac 1 {3}(n+1)^3-\frac 1 {30}(n+1)=$$ $$=\frac 1 {5}n^5+\frac 1 {2}n^4+\frac 1 {3}n^3-\frac 1 {30}n + (n+1)^4$$ calculating the solution with a few additions!

-

Both sides are degree 5 polynomials (the LHS, because it is the discrete integral of a degree 4 polynomial) therefore you can prove the identity always holds by checking it holds for 6 different values of n.

• $n=1$: both sides evaluate 1.
• $n=2$: both sides evaluate to 17.
• $n=3$: both sides evaluate to 98.
• $n=4$: both sides evaluate to 354.
• $n=5$: both sides evaluate to 979.
• $n=6$: both sides evaluate to 2275.

QED

-