Question

Show that 2^2n-1 +1 is divisible by 3 for all n > 1.

Answer 1

Step-by-step explanation:

Let's assume that

$P(n)\ =\ 2^{2n-1}+1$ is divisible by 3.

for n= 1

$P(1)\ =\ 2^{2.(1)-1}+1$

       = 3

Hence, P(1) is true for n=1

for n=2

$P(2)\ =\ 2^{2.(2)-1}+1$

       = 9, which is divisible by 3.

As we can see, P(n) is also true for n= 2.

Let's say P(n) is true for n = k

So,

$P(k)\ =\ 2^{2k-1}+1$ is divisible by 3.

$=>\ P(k+1)\ =\ 2^{2(k+1)-1}+1$

                 $=\ 2^{2k+1}+1$

For P(n) should be true, the difference of P(k+1) and P(k) must will have divisible by 3.

So,

$P(k+1)-P(k)\ =\ 2^{2k+1}+1-(2^{2k-1}+1)$

                  $=\ 2^{2k-1}(2^2-1)$

                  $=\ 3\times 2^{2k-1}$

as P(k+1)-P(k) is divisible by 3.

As a result, P(n) is true for all n>1.