Just a quick question;
How do I show that (1+2+...+n)^2 = 1^3+2^3+...+n^3 ?
The sum on the right can be shoen to be a quartic in $\displaystyle n$ (construct the
difference table and it becomes obviouse).
Which quartic can be established by fitting the first few terms to the
quartic.
The sum on the left is: $\displaystyle \left(\frac{n(n+1)}{2}\right)^2$.
Expand and show the required equality.
RonL
Second method from the department of incredibly elegant but indirect proofs.
The expression on the left is obviously a quartic in n, since the table of
second differences of what is inside the square is constant it is a quadratic in
n and so its square is a quartic in n.
As explained before what is on the right is also a quartic.
To show that two quartics are identical you need only show that they are
equal at five distinct points. So compute the first 5 values of what is on the
left and the corresponding values for what is on the right and if the
corresponding terms are equal the identity is proven.
RonL
Let n = 1.
$\displaystyle (1)^2 = 1^3$? True.
So assume the theorem is true for some n = k. Then we need to prove that it is true for n = k + 1.
Our assumption is that
$\displaystyle (1 + 2 + ~...~ + k)^2 = 1^3 + 2^3 + ~...~ + k^3$
What we wish to prove is
$\displaystyle (1 + 2 + ~...~ + k + (k + 1))^2 = 1^3 + 2^3 +~...~+k^3 + (k + 1)^3$
Now,
$\displaystyle (1 + 2 + ~...~ + k + (k + 1))^2 = (1 + 2 + ~...~ + k)^2 + (k + 1)^2 + 2(1 \cdot (k + 1) + 2 \cdot (k + 1) + ~...~ k(k + 1))$
$\displaystyle = (1^3 + 2^3 + ~...~ + k^3) + (k + 1)^2 + 2(1 \cdot (k + 1) + 2 \cdot (k + 1) + ~...~ k(k + 1))$
according to our assumption. So plugging this back into what we need to prove, we see that we need to show
$\displaystyle = (1^3 + 2^3 + ~...~ + k^3) + (k + 1)^2 + 2(1 \cdot (k + 1) + 2 \cdot (k + 1) + ~...~ k(k + 1))$$\displaystyle = 1^3 + 2^3 +~...~+k^3 + (k + 1)^3$
or
$\displaystyle (k + 1)^2 + 2(1 \cdot (k + 1) + 2 \cdot (k + 1) + ~...~ k(k + 1)) = (k + 1)^3$
So let's work a bit more on that left hand side.
$\displaystyle (k + 1)^2 + 2(1 \cdot (k + 1) + 2 \cdot (k + 1) + ~...~ k(k + 1))$
$\displaystyle = (k^2 + 2k + 1) + 2(k + 1)(1 + 2 + ~...~ + k)$
and the sum of the first k numbers is
$\displaystyle = (k^2 + 2k + 1) + 2(k + 1) \frac{k(k + 1)}{2}$
$\displaystyle = (k^2 + 2k + 1) + k(k + 1)^2$
$\displaystyle = k^2 + 2k + 1 + k^3 + 2k^2 + k$
$\displaystyle = k^3 + 3k^2 + 3k + 1$
$\displaystyle = (k + 1)^3$
as we needed.
So the theorem is true for n = 1 and thus for all integers by induction.
-Dan
First you should know how induction works:
You have a proposition about a netural number n, such as your identity.
Show it holds for a base case, typical n=1 or n=0.
The if you assume that it hold for some k, show this implies it holds for k+1
Then you are done the general proposition is proven for all n greater than or
equal to the base case.
Checking the base case is trivial in this case as for n=1 both sides of the
equality are 1.
I will let you have a go at proving the induction step its not difficult.
RonL