# Thread: proofs by induction

1. ## proofs by induction

i know this is a kind of big list, but i'm completely lost as to how to do these sort of things and i can't seem to make sense of the book (i've spent about 2 hours trying to figure it out)
any help walking me through these would be greatly appreciated

Prove the following by induction:

A) For all integers n >= 0, the number 5^(2n) - 3n is a multiple of 11

B) Any integer n >= 1, 2^(4n-1) ends with an 8

C) The sum of the cubes of three consecutive positive integers is always a multiple of 9

D) If x >= 2 is a real number and n >= 1 is an integer, then x^n >= nx

E) If n >= 3 is an integer, then 5^n > 4^n + 3^n + 2^n

2. Originally Posted by mistykz
i
B) Any integer n >= 1, 2^(4n-1) ends with an 8
Hint: Show that $2^{4n-1} - 8$ is always divisible by $10$.

3. A) Doesn't work. e.g. n=4?

D) $x^n \ge nx$

When x=2 and n=1, $2 \ge 2$ Therefore true for n=1.
Assume it's true for n=k.

$x^k \ge kx$

now for induction, we want to prove that $x^{k+1} \ge k(x+1)$
so here is a standard 'trick' often required for similar questions..

For n=k

$x^k \ge kx$

Times both sides of the inequality by x...

$x^{k+1} \ge kx^2$

But $kx^2 \ge kx$ for x > 0

Add x to both sides.....

$kx^2 + x \ge kx + x$

$x(kx+1) \ge (k+1)x$

Since $x^{k+1} \ge kx^2 \ge (k+1)x$

It is implied, therefore, that $x^{k+1} \ge (k+1)x$ as required.

Hence if n=k is true, then n=k+1 is true. But since n=1 is true, it implies n=2 is true, which implies n=3 is true...etc. Hence proved by induction.

4. awesome, thanks! anyone else got any others?

5. Originally Posted by mistykz
awesome, thanks! anyone else got any others?
Can you show your working for any others you've attempted?

6. well, that's the thing. im stuck as to where to start on any of these. he BRIEFLY flew over the stuff, then tossed this homework in our laps. i just sort of need a little coaxing in the right direction

7. Well, this is not what you'd call 'elegant', but it's a proof of sorts...
Just use the same 'trick' I did for question D.

E) It's easy to prove that the equation is true for n > 2. So I won't waste time or patronise you by proving that. So assume it is true for n=k. Just deal exclusively with the $5^n>4^n$

$5^k>4^k$

multiply each side by 5

$5^{k+1}>20^k$

But for k > 2

$20^k > 4^k$

But $20^k > 16^k$

$20^k > 4^{k+1}$ (Since $4^{k+1} = 4(4^k) = 16^k$ )

Therefore it follows that $5^{k+1} > 20^k > 4^{k+1}$

which implies $5^{k+1} > 4^{k+1}$ as required. Hence if n=k is true, then n=k+1 is true. But since n=1 is true, it implies n=2 is true, which implies n=3 is true...etc.

Repeat the process for $4^n > 3^n$ then $3^n > 2^n$. If you want more help, I'd more more than willing to provide it - but can you at least try to say anything you don't understand - or better yet, post some working, that would be great.

8. Hello, mistykz!

C) The sum of the cubes of three consecutive positive integers is always a multiple of 9
Let the three consecutive cubes be: . $(n-1)^3,\;n^3,\;(n+1)^3$

We want to show that: . $(n-1)^3 + n^3 + (n+1)^3 \:=\:9a$ .for some integer $a.$

Vertify $S(1)\!:\;\;(1-1)^3 + (1)^2 + (1+1)^3 \;=\;0^3 + 1^3 + 2^3 \;=\;9$ . . . yes!

Assume $S(k)\!:\;\;(k-1)^3 + k^3 + (k+1)^3 \;=\;9a$ .for an integer $a.$

Add $-(k-1)^3 + (k+2)^3$ to both sides:
. . $(k-1)^3 {\color{blue}\,-\, (k-1)^3} + k^3 + (k+1)^3 {\color{blue}\,+\, (k+2)^3} \;=\;9a {\color{blue}\,-\, (k-1)^3 + (k+2)^3}$

and we have:
. . $k^3\,+\,(k+1)^3\,+\,(k+2)^3 \;=\;9a\,-\,k^3\,+\,3k^2\,-\,3k\,+\,1\,+\,k^3\,+\,6k^2\,+\,12k\,+\,8 \;= \;9a$ $+\,9k^2\,+\,9k\,+\,9$

Therefore: . $k^3 + (k+1)^3 + (k+2)^3 \;=\;9(a + k^2 + k + 1)$ . . . . a multiple of 9

The induction proof is complete.