<s>[INST] 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?
 [/INST] 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.$
</s>