Two Simple Induction Proofs

1. Jan 21, 2008

steelphantom

1. The problem statement, all variables and given/known data
Prove 1^3 + 2^3 + ... + n^3 = (1 + 2 + ... + n)^2 for all natural numbers n.

2. Relevant equations

3. The attempt at a solution

Well, this seems like the typical induction proof, so I start by testing the hypothesis at 1: 1^3 = 1^2 = 1. Then I assume that the equation is true for n, and try to prove it true for n + 1.

1 ^3 + 2^3 + ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n)^2 + (n + 1)^3

I have this, but how do I get it to be (1 + 2 + ... + n + n + 1)^2? Is it some crazy factorization that I'm overlooking? It seems pretty easy.

1. The problem statement, all variables and given/known data

Prove that 7^n - 6n - 1 is divisible by 36 for all positive integers n.

2. Relevant equations

3. The attempt at a solution

Well, the statement seems to be saying the following: 7^n - 6n - 1 = 36k, where k is a positive integer. As with the first problem, testing it with 1 works. Assuming it is true for n + 1 would mean the following, if I'm correct:

7^(n + 1) - 6(n + 1) - 1 = 36j, where j is a positive integer. At this point, I'm not sure how to proceed.

I know I'm probably overlooking some obvious stuff here, so a little hint is probably all I'll need to finish these problems off. Thanks! :)

2. Jan 21, 2008

Mathdope

Try to substitute something else for (1+2+...+n). The formula for it is not that hard to derive.
7^(n+1) = 7^n*7. You are assuming that 7^n = 36k + 6n + 1. See what happens.

3. Jan 21, 2008

rock.freak667

$$1^3 + 2^3 + ... + n^3=\sum_{n=0} ^{N} n^3$$

$$(1 + 2 + ... + n)^2 =(\sum_{n=0} ^{N} n)^2$$

Do you know what $\sum_{n=0} ^{N} n$ represents?

4. Jan 22, 2008

steelphantom

Thanks guys for your help! I solved the second problem. The first problem is still puzzling me a bit. Here's what I have:

$$1^3 + 2^3 + ... + n^3 = \sum_{n=0} ^{N} n)^2 + (n + 1)^3$$

Still not sure how to add those two terms together. I'm sure it's very easy, but I'm just not seeing it.

5. Jan 22, 2008

HallsofIvy

Staff Emeritus
The same question, again, can you write
$\sum_{n=0}^N n$
in a "closed" form and then square?

6. Jan 22, 2008

steelphantom

Got it! Thank you. :)