How can I solve a complicated induction exercise? (formula for sum of fourth powers) I have an induction exercise:
It is for $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 I 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?
 A: 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.
A: $\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.
A: 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!
A: 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.$
A: 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
