x Turn on thread page Beta
 You are Here: Home >< Maths

# proof by induction problem watch

1. prove that for all natural values of n, 64 | [(9^n)-8n-1]

i got to 9^(n+1) - 8(n+1) -1 = 64k + 8(9^n) -8

but taking a factor of 64 out leaves u with eighths inside the bracket-does this prove the statement in bold?? or have i just made a total mess of it?!

any help would be much appreciated
2. I don't understand what you have to prove? 64 | [(9^n)-8n-1] ??

What does this mean?
3. that 64 divides the expression
prove that for all natural values of n, 64 | [(9^n)-8n-1]

i got to 9^(n+1) - 8(n+1) -1 = 64k + 8(9^n) -8

but taking a factor of 64 out leaves u with eighths inside the bracket-does this prove the statement in bold?? or have i just made a total mess of it?!

any help would be much appreciated
8(9^n)-8 = 8(9^n -1 ), now 9^n -1 is divisible by 8 for all n (factorise), so you can write it as 64m for some m.
5. [9^(n + 1) - 8(n + 1) - 1] - [9^n - 8n - 1]
= 8*9^n - 8
= 8((9^n) - 1)
= 8(9 - 1)[9^(n - 1) + 9^(n - 2) + ... + 9 + 1]
= 64 [9^(n - 1) + 9^(n - 2) + ... + 9 + 1]

is divisible by 64. The result follows by induction.
6. sorry how did u get from this line = 8((9^n) - 1)

to this one = 8(9 - 1)[9^(n - 1) + 9^(n - 2) + ... + 9 + 1] ??
7. oh rite i get u! sorry never seen that before
8. 9^(n+1) - 8(n+1) -1 = 9(9^n - 8n -1) - 64n
9. prove that for all natural values of n, 64 | [(9^n)-8n-1]

Here's what I got then.

Works for n = 1:

9^1 - 8*1 - 1 = 0
this divides 64

Now assume it works for all natural values of n:

64 divides (9^n - 8n - 1)

That is, for any positive integer a,

64a = 9^n - 8n - 1
9^n = 64a + 8n + 1

Now the proof that if it is true for one natural number n, it is also true for n+1 - that:

64 also divides (9^(n+1) - 8(n+1) - 1)

9^(n+1) - 8(n+1) - 1 = 9*9^n - 8n - 9 = (64a + 8n + 1) - 8n - 1 = 64a

Shown.
10. To prove this without induction consider the binomial expansion of (8+1)^n. Except for the last two terms the power of 8 in each term is at least two. That is,

(8+1)^n = 8^n + (nC1)8^(n-1) + (nC2)8^(n-2) + ... + (nC3)8^3 + (nC2)8^2 + (nC1)8 + 1
= K(8^2) + 8n + 1

where (nCr) represents the binomial coefficients and K is some integer. This result rearranges to give

9^n - 8n - 1 = 64K

which is what we wanted.

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 17, 2004
Today on TSR

### Loughborough better than Cambridge

Loughborough at number one

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams