# proof by induction problem

Watch
Announcements
This discussion is closed.
#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
0
15 years ago
#2
I don't understand what you have to prove? 64 | [(9^n)-8n-1] ??

What does this mean?
0
#3
that 64 divides the expression
0
15 years ago
#4
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.
0
15 years ago
#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.
0
#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] ??
0
#7
oh rite i get u! sorry never seen that before
0
15 years ago
#8
9^(n+1) - 8(n+1) -1 = 9(9^n - 8n -1) - 64n
0
15 years ago
#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.
0
15 years ago
#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.
0
X
new posts Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### If you're planning on going to uni this year, would any of these financial reasons stop you?

Not being able to work now to save up for uni (92)
13.94%
Reduced household income due to coronavirus means I can't afford to go (54)
8.18%
Lack of part-time jobs to support me while I'm at uni (85)
12.88%
Lack of graduate job prospects when I finish uni (79)
11.97%
Other reasons are stopping me going (84)
12.73%
Nothing is stopping me going (266)
40.3%