Help with proof by mathematical induction

[IBVeryStressed]

I need to prove that 2²ⁿ-3n-1 is divisible by 9

I already proved it true for n=1 and assumed true for n=k

It's proving it true for n= k+1 that's giving me problems

[kiwi.at.heart]

If you got the question from questionbank this will be useless but if you didn't this is the mark scheme given on questionbank however i cant see how they get from the 3rd red line to the last red line but you may be able to. I hope this helps.

Let S(n) be the statement: 22n – 3n – 1 is divisible by 9.

Since 22 – 3 – 1 = 0, S(1) is true. (C1)

Assume as the induction hypothesis S(k) ie 22k – 3k – 1 is divisible by 9. (C1)

We shall show that S(k + 1) is true.

S(k + 1) = 2^2(k+l) – 3(k + 1) – 1 (M1)

= 4(2^2k) – 3k – 4 (M1)

= 9(2^2k – 3k – 1) + 9k (A1)

By the induction hypothesis 22k – 3k – 1 is divisible by 9.

Since 9k is also divisible by 9, S(k + 1) is true. (M1)

Thus, by mathematical induction S(n) is true, n = 1, 2, ... (R1)

Edited January 6, 2011 by Kiwiatheart

[genepeer]

We shall show that S(k + 1) is true.

S(k + 1) = 2^2(k+l) – 3(k + 1) – 1 (M1)

= 4(2^2k) – 3k – 4 (M1)

= 9(2^2k – 3k – 1) + 9k (A1)

That last line should be

= 4(2^2k – 3k – 1) + 9k (A1)

Edited January 6, 2011 by Gene-Peer

[kiwi.at.heart]

That last line should be

= 4(2^2k – 3k – 1) + 9k (A1)

No, it was copied and pasted straight from the Maths HL QuestionBank, and I have yet to find any errors there. There answer looks confusing, but its correct, I just dont know how they get there. I was doing revision a bit ago and this question stumped me too.

[genepeer]

However rare it occurs, they can still make mistakes you know, esp. typing 9 instead of 4 because you're thinking "divisible by 9". How about this? Expand what you wrote, and expand what I wrote and see which one gives a statement equivalent to the previous one.

Edited January 6, 2011 by Gene-Peer

[kiwi.at.heart]

You are right, I'm looking back on it now and it now makes sense. Sorry

[anonymous4]

2^(2n) -3n-1 is divisible by 9:

Need to show the for n =2, the statement above is true.

2^(2 * 2) - 3 (2) -1=

2^4 - 6 - 1=

16-7=

9.

therefore, the statement is true for n = 2

Assume that the statement is true for n = k

If some number is divisible by 9, it will be in the form 9A where A is a natural number greater than 2

2^(2k) -3k - 1 = 9A ( induction hypothesis)

prove the statement for P(k+1)

2^(2(k+1)) - 3 ( k+1) -1=

2^(2k+2) - 3k - 3 - 1 =

(2^(2k))(2^2) - 3k - 4 =

(2^2k)4 - 3k - 4 =

Consider the induction hypothesis :

2^(2k) -3k - 4 = 9A

2^(2k) = 9A - 3k +1 -----> substitute induction hypothesis into the function of p ( k+1) and thence show that the statement is true.

(2^2k)4 - 3k - 4 =

(9A - 3k +1 )(4) - 3k - 4 =

36A - 12k +4 -3k + 4 =

36A - 9k=

9( 4A - k).

and as previously stated, for a number to be divisible by 9, it must be in the form 9A where A is a natural number greater than two, and we see from the last step that

the correct form is shown.

[heyit'salison]

Prove by mathematical induction that 2²ⁿ - 3n - 1 is divisible by 9:

n = 1:

2²⁽¹⁾ - 3(1) - 1

= 4 - 3 - 1

= 0

which is divisible by 9 (remember 0 is divisible by any number)

n = k:

2^2k - 3k - 1 = 9A

2^2k = 9A + 3k + 1

where 'A' is any number where when expanded, will be a multiple by 9

n = k + 1:

2^2(k+1) - 3(k + 1) - 1

= 2^{2k + 2} - 3k - 3 - 1

= 2^2k x 2² - 3k - 4

from n = k, we know that 2^2k = 9A + 3k + 1

therefore by substitution:

= 2²(9A + 3k + 1) - 3k - 4

= 4(9A + 3k + 1) - 3k - 4

= 36A + 12k + 4 - 3k - 4

= 36A + 9k

= 9(4A + k)

therefore since P_k+1 is true when P_{k is true} and P₁ is true, 2²ⁿ - 3n - 1 is divisible by 9

Edited April 26, 2011 by heyit'salison