# 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. :)