Question

Using mathematical induction prove that 4^n - 3n -1 is divisible by 9

Answer 1

let P(n):4^n-3n-1 is divisible by 9
for n=1,P(1) is divisible by n
so P(n) is true for n=1
now we shall assume tharfor n=k, P(k):4^k-3k+1 is divisible by 9
and 4^k-3k-1=9m
4^k=9m+3k+1 (1)
now we shall prove that P(n)is also true for n=k+1
P(k+1):4^(k+1)-3(k+1)-1=4^k.4-3k-3-1
from(1),(9m+3k+1)4-3k-4=36m+12k+4-3k-4=
36m+9k=9(4m+k) which is divisible by 9
so P(k+1) is true whenever P(k) is true
P(n) is true for all n€N

Answer 2

Let,

S(n) be the statement

S(n) = $\sf4^n-3n-1$ is divisible by 9

For n = 1

$\sf S(1) = \sf4^1-3(1)-1$

$\sf \qquad = 4 - 4 = 0$ is divisible by '9'

S(1) is true for n = 1

Let us asume that,

Given statement is true for n = k

S(k) = $\sf4^k-3k-1$ is divisible by 9

$\sf \qquad 4^k-3k-1=9k$ (where k ∈ N)

We have to prove that,

The statement is true for n = k+1

S(k+1) = $\sf4^{k+1}-3(k+1)-1$ $\qquad ( \sf a^m.a^n=a^{m+n})$

$\qquad\sf = 4^{k}.4^{1}-3k-3-1$

$\qquad\sf = (9t+3k+1) 4-3k-4$

$\qquad\sf = 36t+12k+4-3k-4$

$\qquad\sf = 36t+9k$

$\qquad\sf = 9(4t+k)k$

∴ S(k+1) is divisible by 9

It is true for n=(k+1)

By using principle of mathematical induction,

∴ The given statement S(n) is true ∀ n ∈ N

$\:$