# proofs by induction

• Sep 24th 2007, 03:14 PM
mistykz
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
• Sep 24th 2007, 05:43 PM
ThePerfectHacker
Quote:

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$.
• Sep 24th 2007, 06:08 PM
WWTL@WHL
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

$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.
• Sep 24th 2007, 07:26 PM
mistykz
awesome, thanks! anyone else got any others?
• Sep 24th 2007, 07:29 PM
WWTL@WHL
Quote:

Originally Posted by mistykz
awesome, thanks! anyone else got any others?

Can you show your working for any others you've attempted? :)
• Sep 24th 2007, 07:35 PM
mistykz
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
• Sep 25th 2007, 03:50 AM
WWTL@WHL
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. :)
• Sep 25th 2007, 05:14 AM
Soroban
Hello, mistykz!

Quote:

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.