proofs by induction

**mistykz** · September 24th 2007, 02:14 PM

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

**ThePerfectHacker** · September 24th 2007, 04:43 PM

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$ .

**WWTL@WHL** · September 24th 2007, 05:08 PM

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.

**mistykz** · September 24th 2007, 06:26 PM

awesome, thanks! anyone else got any others?

**WWTL@WHL** · September 24th 2007, 06:29 PM

Originally Posted by mistykz

awesome, thanks! anyone else got any others?

Can you show your working for any others you've attempted?

**mistykz** · September 24th 2007, 06:35 PM

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

**WWTL@WHL** · September 25th 2007, 02:50 AM

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.

**Soroban** · September 25th 2007, 04:14 AM

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.

Thread: proofs by induction

LinkBack

Thread Tools

Display

proofs by induction

Similar Math Help Forum Discussions

Proofs by Induction

Induction proofs

proofs by induction

Induction Proofs

A couple induction set proofs

Search Tags