# proofs by induction

• Sep 24th 2007, 02: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, 04:43 PM
ThePerfectHacker
Quote:

Originally Posted by mistykz
i
B) Any integer n >= 1, 2^(4n-1) ends with an 8

Hint: Show that \$\displaystyle 2^{4n-1} - 8\$ is always divisible by \$\displaystyle 10\$.
• Sep 24th 2007, 05:08 PM
WWTL@WHL
A) Doesn't work. e.g. n=4?

D) \$\displaystyle x^n \ge nx\$

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

\$\displaystyle x^k \ge kx \$

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

For n=k

\$\displaystyle x^k \ge kx\$

Times both sides of the inequality by x...

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

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

Add x to both sides.....

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

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

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

It is implied, therefore, that \$\displaystyle 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, 06:26 PM
mistykz
awesome, thanks! anyone else got any others?
• Sep 24th 2007, 06: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, 06: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, 02: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 \$\displaystyle 5^n>4^n\$

\$\displaystyle 5^k>4^k\$

multiply each side by 5

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

But for k > 2

\$\displaystyle 20^k > 4^k\$

But \$\displaystyle 20^k > 16^k \$

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

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

which implies \$\displaystyle 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 \$\displaystyle 4^n > 3^n \$ then \$\displaystyle 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, 04: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: .\$\displaystyle (n-1)^3,\;n^3,\;(n+1)^3\$

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

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

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

Add \$\displaystyle -(k-1)^3 + (k+2)^3\$ to both sides:
. . \$\displaystyle (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:
. . \$\displaystyle k^3\,+\,(k+1)^3\,+\,(k+2)^3 \;=\;9a\,-\,k^3\,+\,3k^2\,-\,3k\,+\,1\,+\,k^3\,+\,6k^2\,+\,12k\,+\,8 \;= \;9a\$ \$\displaystyle +\,9k^2\,+\,9k\,+\,9\$

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

The induction proof is complete.