Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

5 Answers 5

up vote 1 down vote accepted

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.$

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

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!

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.