# mathematical induction problem...help?

prove by mathematical induction 10^n+ 3.4^(n+2) + 5 is divisible by 9

Relevance

Let's take p(1); here, n = 1

LHS : 10^1 + 3 x 4^(1+2) + 5

= 10 + 3 x 4^3 + 5

= 15 + 3 x 64

= 15 + 192

= 207

Now, if LHS is divisible by 9, remainder = 0

207 / 9 : Q = 23 and R = 0

Therefore, LHS = RHS and p(1) is true...

Now we assume that p(k) is true; here, k ∈ N

So, 10^k + 3 x 4^(k+2) + 5 is divisible by 9

=> 10^k + 3 x 4^(k+2) + 5 = 9m ; let m be any natural number...(it can vary)

=> 10^k = 9m - 3 x 4^(k+2) - 5 ; Subtract 3 x 4^(k+2) + 5 from both sides - (1)

Now, we've to prove that p(k+1) is true ; here k + 1 = n and k ∈ N

10^n + 3 x 4^(n+2) + 5

= 10^(k+1) + 3 x 4^(k+1+2) + 5---{As we said that n = k+1}

= 10^k x 10 + 3 x 4^(k+3) + 5

= ( 9m - 3 x 4^(k+2) - 5)x10 + 3x4^(k+3) + 5 ---{We put 10^k from (1) here...}

= 9(10m) - 3x10 x 4^(k+2) - 50 + 3x4^(k+3) + 5

= 9(10m) - 3x10x4^(k+2) + 3x4^(k+2)x4 - 45

= 9(10m) - 3 x 4^(k+2)x(10-4 ) - 45 ---{Take 3 x 4^(k+2) common}

= 9(10m) - 9(5) - 18 x 4^(k+2) ---{as 45 = 9(5) }

= 9(10m) - 9(5) - 9(3x4^(k+2)) ---{as 18 = 9x3}

= 9(10m - 5 - 3x4^(k+2)) ---{Take 9 common from all 3 terms...}

That's it... Let 10m - 5 - 3^4(k+2) be any variable Natural number, p

=9p => It's divisible by 9...

Therefore, p(k+1) is true...

And by the Principle of Mathematical Induction, and for all true values of k, p(k+1) is true, p(n) is true. This means that the formula is proved!

Hope this helps...

Source(s): My love for math and Mathematical Induction...
• Let P(n) be the predicate such that

10^n + 3(4^(n + 2)) + 5 is divisible by 9

for all n ≥ 0

The basic step, prove that P(0) is true

10^0 + 3(4^(0 + 2)) + 5 = 54

9 | 54

so P(0) is true

Now assume P(k) is true

then

10^k + 3(4^(k + 2)) + 5 must be divisible by 5

Then we must prove that P(k + 1) is also true

P(k + 1)

= 10^(k + 1) + 3(4^(k + 3)) + 5

= (10^k)(10^1) + 3(4^(k + 2))(4^1) + 5

= 10(10^k) + 3(4^(k + 2))(4) + 5

= 9(10^k) + (10^k) + 12(4^(k + 2)) + 5

= 9(10^k) + (10^k) + 3(4^(k + 2)) + 9(4^(k + 2)) + 5

= [ 9(10^k) + 9(4^(k + 2)) ] + (10^k) + 3(4^(k + 2)) + 5

= 9 [ (10^k) + (4^(k + 2)) ] + [ (10^k) + 3(4^(k + 2)) + 5 ]

Since 9 [ (10^k) + (4^(k + 2)) ] is divisible by 9 as it has a factor of 9 when factorized, and we assumed P(k) is true or [ (10^k) + 3(4^(k + 2)) + 5 ] is divisible by 9

Both the terms in P(k + 1) is divisible 9, which makes P(k + 1) divisible by 9, thus P(k + 1) is valid

P(k) ==> P(k + 1)

Hence this concludes the proof.

• Mistake: it should be 10^n+3*4^(n+2)+5 not "3.4^(n+2)".

Let p(n)="10^n+3*4^(n+2)+5 is divisible by 9".

p(1):10^4+3*4^3+5

=10197 is divisible by 9 (1+1+9+7=18)=>

p(1) is true.

Assume p(k) is true for k>=1, where k is an integer. Then

p(k+1):10^(k+1)+3*4^(k+2)+5

=10*10^k+3[(4^(k+1))*(3+1)]+5

=9*10^k+9*4^(k+1)+[10^k+3*4^(k+1)+5]

is divisible by 9 =>

p(k+1) is true too

So, p(n) is true for any +ve integer n.

• Anonymous
9 years ago

Mistake: it should be 10^n+3*4^(n+2)+5 not "3.4^(n+2)".

Let p(n)="10^n+3*4^(n+2)+5 is divisible by 9".

p(1):10^4+3*4^3+5

=10197 is divisible by 9 (1+1+9+7=18)=>

p(1) is true.

Assume p(k) is true for k>=1, where k is an integer. Then

p(k+1):10^(k+1)+3*4^(k+2)+5

=10*10^k+3[(4^(k+1))*(3+1)]+5

=9*10^k+9*4^(k+1)+[10^k+3*4^(k+1)+5]

is divisible by 9 =>

p(k+1) is true too

So, p(n) is true for any +ve integer n.