# Need help with simple proof by mathematical induction

$$\sum_{k=1}^n k^4 = {(6n^5+15n^4+10n^3-n) \over 30}$$

How can this be proven using mathematical induction? My teacher isn't any help, he just tells me to think about it, but I've read the textbook again and again, and there isn't much in it that would help me prove this statement.

*Sorry to ask multiple questions on the site in such a short time, but I'm just quite desperate for help and I don't have anyone to go to for it. My teacher barely speaks English, and with my poor hearing I can hardly follow the class and I need to pass this exam desperately.

-
What have you tried so far? Have you checked the base case (when $n = 1$)? Have you written out the inductive hypothesis (suppose the identity holds for $n$). Have you then written out what you are trying to prove (what does the identity say for $n+1$?)? How can you prove this using your inductive hypothesis? –  Benjamin Dickman Dec 10 '12 at 20:29
I think your instructor is right. Every induction proof is almost identical. Just follow the general procedure. –  glebovg Dec 10 '12 at 20:34
"Every induction proof is almost identical" Hehe... –  Andres Caicedo Dec 10 '12 at 21:03
I would say that the generalization that "every induction proof is identical" is a very poor generalization, and still doesn't help much with learning how to think about these kinds of problems. I'm guessing that what you've done already and the answers provided you have a template for the proof, and now mainly aren't sure of the inner mechanics of this type of problem. In the real world these mechanics are the primary area variation of inductive proofs themselves. In your class (it would seem) practicing polynomial arithmetic is likely going to be a big push to understanding these mechanics. –  Vilid Dec 10 '12 at 21:13

I think your teacher is right, but anyway...

Basic step ($n_0=1$):

Left side:

$\sum_{k=1}^1 k^4 = 1$

Right side:

${(6+15+10-1) \over 30} = 1$

Left and right side are equal. Done.

Induction step:

Assuming it works for $n$, try to show it works for $n+1$ aswell.

So we have:

$\sum_{k=1}^{n+1} k^4 = {(6(n+1)^5+15(n+1)^4+10(n+1)^3-(n+1)) \over 30}$

which is the same as:

$(n+1)^4 + \sum_{k=1}^{n} k^4 = {(6(n+1)^5+15(n+1)^4+10(n+1)^3-(n+1)) \over 30}$

Now take this term (the last of the sum) to the other side of the equation: $\sum_{k=1}^{n} k^4 = {(6(n+1)^5+15(n+1)^4+10(n+1)^3-(n+1)) \over 30} - (n+1)^4$

And after some basic algebra you get back to:

$\sum_{k=1}^n k^4 = {(6n^5+15n^4+10n^3-n) \over 30}$

which is precisely what we want.

Now since we have shown that it works for 1 in the first step, we can argue that it works for 2, and since it works for 2 it works for 3 - and so on :)

-
Thank you so much! I get it now! :D –  user52527 Dec 10 '12 at 21:47

Theorem (Principle of mathematical induction):

Let $G\subseteq \mathbb{N}$, suppose that

a. $1\in G$
b. if $n\in \mathbb{N}$ and $\{1,...,n\}\subseteq G$, then $n+1\in G$

Then $G=\mathbb{N}$

step 0: First of all define $P(n)$ for some $n\in \Bbb{N}$, for example: $$\mbox{let}\,\,P(n)\,\,\mbox{be the statement}: \sum_{k=1}^n k^4 = {(6n^5+15n^4+10n^3-n) \over 30}$$

step 1:(Basis step) Start the proof by proving this for $P(1)$ (this means prove that the statement $P(n)$ is true for $n=1$)

Thus we want to show that the LHS=RHS for $n=1$.

step 2: Assume that $P(n)$ is true for some $n\in\Bbb{N}$.

step 3: Prove the statement for $P(n+1)$ (you will need step 2 for this)

Thus we want to show that the LHS=RHS for $n+1$.

Conclusion: Hence, if $P(n)$ is true, then $P(n+1)$ is true. Therefore: \begin{array}{|1|} \hline \sum_{k=1}^n k^4 = {(6n^5+15n^4+10n^3-n) \over 30}; \qquad\forall n\in\Bbb{N}\\ \hline \end{array}

-
I think you got the second step wrong, you assume what you want to prove –  Belgi Dec 10 '12 at 21:14
@Belgi: That is how induction works. You assume that $P(n)$ is true for some $n$ and deduce that $P(n+1)$ is true. –  robjohn Dec 10 '12 at 22:34

Prove first that the formula holds for n=1. This is your base case.

The next (and the last) thing you have to show is:

whenever the formula holds for an arbitrary value of n, it holds for the value n+1-- right after that.

Having proved these two, you'll have proved each step holds the next and thus the base case holds it all recursively.

-

For any induction proof you should try to do the following:

Prove the base case,
Prove that assuming the claim for $n=N$ implies the claim holds for $n=N+1$.

For the base case let $n=1$. You get $1=\frac{6+15+10-1}{30}$, which is true.
Now assume that the sum is indeed given by your formula. Then $$\sum_{k=1}^{N+1}k^{4}=\sum_{k=1}^{N}k^{4}+(N+1)^{4}=\frac{6N^{5}+15N^{4}+10N^{3}-N}{30}+(N+1)^{4}$$ By our initial assumption. We can bring these over a common denominator and expand (using the binomial theorem) to get
$$\frac{6N^{5}+15N^{4}+10N^{3}-N+30N^{4}+120N^{3}+180N^{2}+120N+30}{30}$$ Collecting like terms gives $$\frac{6N^{5}+45N^{4}+130N^{3}+180N^{2}+119N+30}{30}$$ Show that this is equal to $$\frac{6(N+1)^{5}+15(N+1)^4+10(N+1)^3-(N+1)}{30}$$ And you're done!

-

General porcedure: Denote the left hand side as $f(n)$, the right hand side as $g(n)$. Show that $f(0)=g(0)$. Then show that for each $n$ you have $f(n)-f(n-1)=g(n)-g(n-1)$. Note that $f(n)-f(n-1)=n^4$.

-