Question

Show that $2^{2n}-3n-1$ is divisible by $9$ for all positive integral values of $n$.

Answer 1

We will prove this by induction.

Let $I=2^{2n}-3n-1=4^n-3n-1$

For $n=1$, $I=4-3-1=0$ and zero is divisible by 9.

Now, let us assume $I$ to be divisible by $9$ for some $n=k$.

That is $I=4^k-3k-1=9\times r$ ------(1) (where r is any integer)

We need to prove that $I$ is divisible by $9$ for $n=k+1$

$I=4^{k+1}-3(k+1)-1=4\times 4^k-3k-4$

$=4(4^k-1)-3k$

Replace $4^k-1=9r+3k$ ----by using eq. (1),

We get $I=4(9r+3k)-3k=36r+12k-3k=36r+9k=9(4r+1)$

$r$ is an integer, therefore $4r+1$ is also an integer and hence

$9(4r+1)$ is also an integer.

Hence for $n=k+1$, $I$ is divisible by $9$.

Hence by induction, we have proved that $2^{2n}-3n-1$ is divisible by 9.