1. divisible by 9

Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

2. First of all we have that

$\displaystyle 4^n-1=(4-1)(4^{n-1}+4^{n-2}+\ldots+4+1)=3(4^{n-1}+4^{n-2}+\ldots+4+1)=3a$

Now

$\displaystyle 2^{2n}-3n-1=(4^n-1)-3n=3(4^{n-1}+4^{n-2}+\ldots+4+1)-3n=$

$\displaystyle =3(4^{n-1}+4^{n-2}+\ldots+4+1-n)=$

$\displaystyle =3[(4^{n-1}-1)+(4^{n-2}-1)+\ldots+(4-1)]=$

$\displaystyle =3(3a_1+3a_2+\ldots+3a_{n-1}+3)=9(a_1+a_2+\ldots+a_{n-1}+1)$

3. Originally Posted by john_n82
Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

proof by induction

n=1
$\displaystyle 2^2-3(1)-1=0$ and 0 is divisable by 9

assume n=k

$\displaystyle 2^{2k}-3k-1$ is divisable by 9

Show k+1

$\displaystyle 2^{2(k+1)}-3(k+1)-1=2^{2k+2}-3k-4=4\cdot 2^k-3k-4$

Now we want to use the induction hypothesis so we will fix up the equation so we can

$\displaystyle 4\cdot(2^k-3k-1)-4\cdot (-3k)-4\cdot(-1)-3k-4=4\cdot(2^k-3k-1)+9k$

so the first term is divisable by 9 by the induction hypothesis and 9k is obviously divisable by 9 so we are done.

4. red_dog and TheEmptySet,

thank you for your super help.

JN

5. Re: Divisibility question...

Originally Posted by john_n82
Prove that 2^(2n) - 3n - 1 is divisible by 9 for all n in N. (Hint: 2^(2n) = (3+1)^n)

I believe that this proof could be approached a couple of different ways. Below I use modular arithmatic and the idea of congruency for the proof.

$\displaystyle \text{THM}:\text{ }9\left| 2^{2n}-3n-1 \text{for} \forall n\in \mathbb{N}\right.$

PF: $\displaystyle \text{Let} n\in \mathbb{N}.$ Then n must be congruent to one of the following
0 , 1, 2, 3, 4, 5, 6, 7, 8 (mod 9).

$\displaystyle \text{If} n \equiv 0 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(0)}-3(0)-1 = 0 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 1 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(1)}-3(1)-1 = 0 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 2 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(2)}-3(2)-1 = 9 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 3 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(3)}-3(3)-1 = 54 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 4 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(4)}-3(4)-1 = 243 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 5 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(5)}-3(5)-1 = 1008 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 6 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(6)}-3(6)-1 = 4077 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 7 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(7)}-3(7)-1 = 16362 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 8 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(8)}-3(8)-1 = 65511 \equiv 0 (\text{mod} 9)$

In all cases, $\displaystyle 2^{2n}-3n-1\equiv 0 (\text{mod} 9).\text{ }\text{Therefore} \text{ }2^{2n}-3n-1 \text{ }\text{is} \text{ }\text{divisible} \text{ }\text{by} \text{ }9\therefore$

--------------------------------
Josh
--------------------------------

6. Originally Posted by Invertible
I believe that this proof could be approached a couple of different ways. Below I use modular arithmatic and the idea of congruency for the proof.

$\displaystyle \text{THM}:\text{ }9\left| 2^{2n}-3n-1 \text{for} \forall n\in \mathbb{N}\right.$

PF: $\displaystyle \text{Let} n\in \mathbb{N}.$ Then n must be congruent to one of the following
0 , 1, 2, 3, 4, 5, 6, 7, 8 (mod 9).

$\displaystyle \text{If} n \equiv 0 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(0)}-3(0)-1 = 0 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 1 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(1)}-3(1)-1 = 0 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 2 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(2)}-3(2)-1 = 9 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 3 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(3)}-3(3)-1 = 54 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 4 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(4)}-3(4)-1 = 243 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 5 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(5)}-3(5)-1 = 1008 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 6 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(6)}-3(6)-1 = 4077 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 7 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(7)}-3(7)-1 = 16362 \equiv 0 (\text{mod} 9)$
$\displaystyle \text{If} n \equiv 8 (\text{mod} 9), \text{then}\text{ }2^{2n}-3n-1\equiv 2^{2(8)}-3(8)-1 = 65511 \equiv 0 (\text{mod} 9)$

In all cases, $\displaystyle 2^{2n}-3n-1\equiv 0 (\text{mod} 9).\text{ }\text{Therefore} \text{ }2^{2n}-3n-1 \text{ }\text{is} \text{ }\text{divisible} \text{ }\text{by} \text{ }9\therefore$

--------------------------------
Josh
--------------------------------
Josh, thank you for helping me. I think i could use this method to approach similar problems for small integers, right?

7. Originally Posted by john_n82
Josh, thank you for helping me. I think i could use this method to approach similar problems for small integers, right?
Yes. To use congruency, you have to show that every possible remainder is equivelent to 0 (mod 9). The bigger the devisor, the more remainders you will have to test.

8. Originally Posted by john_n82
(Hint: 2^(2n) = (3+1)^n)
Observe that all the terms in the binomial expansion of $\displaystyle (3+1)^n$ are divisible by 9 except the first two. Hence

$\displaystyle 2^{2n}=(3+1)^n\equiv3n+1\pmod9$*

$\displaystyle \therefore\ 2^{2n}-3n-1\equiv0\pmod9$*

– in other words, $\displaystyle 2^{2n}-3n-1$ is divisible by 9.

*Another way of writing it out:

$\displaystyle 2^{2n}\ =\ (3+1)^n\ =\ \underbrace{3^n+n\cdot3^{n-1}+\cdots+\binom{n}{2}3^2}_{\textrm{divisible by 9}}+3n+1$

$\displaystyle \therefore\ 2^{2n}-3n-1\ =\ \underbrace{3^n+n\cdot3^{n-1}+\cdots+\binom{n}{2}3^2}_{\textrm{divisible by 9}}$