Divisibility by 6

**aonin** · April 9th 2011, 05:45 AM

Hey guys I need help with this question

$\text{prove} <br /> (4^{n}-1)(3^{n}-1) \text{is divisible by 6 for all positive values of n, without Induction}$

and the answer given in the solution to the question is that since

$4^{n}-1=(1+3)^{n}-1 \therefore \text{Divisble by 3}$
$3^{n}-1=(1+2)^{n}-1 \therefore \text{Divisble by 2}$

$\therefore\text{Product is divisble of 2 and 3, therefore divisble by 6}$

I know by substituting in values for n in $(1+3)^{n}-1$ that they all appear divisible by 3, is this a definite rule, is there a proof of this without using induction?

The same goes for $(1+2)^{n}-1$ , how do we know that this is divisble by 2 for all values of n without induction

If we can't use induction to prove those divisbility by 3 and 2, then isn't the question kinda invalid?

Thanks

**veileen** · April 9th 2011, 06:18 AM

1.
I guess you don't know Newton's generalized binomial theorem...

$(a+b)^n=M_a+b^n=M_b+a^n$
I considered $M_k$ a multiple of k.

So:
$4^n-1=(1+3)^n-1=M_3+1-1=M_3$
$3^n-1=(1+2)^n-1=M_2+1-1=M_2$

2.
$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+ab^{n-2}+b^{n-1})$

So:
$4^n-1=(4-1)(4^{n-1}+4^{n-2}+...+4+1)=3(4^{n-1}+4^{n-2}+...+4+1)$
$3^n-1=(3-1)(3^{n-1}+3^{n-2}+...+3+1)=2(3^{n-1}+3^{n-2}+...+3+1)$

**topsquark** · April 9th 2011, 06:21 AM

Originally Posted by aonin

Hey guys I need help with this question

$\text{prove} <br /> (4^{n}-1)(3^{n}-1) \text{is divisible by 6 for all positive values of n, without Induction}$

and the answer given in the solution to the question is that since

$4^{n}-1=(1+3)^{n}-1 \therefore \text{Divisble by 3}$
$3^{n}-1=(1+2)^{n}-1 \therefore \text{Divisble by 2}$

$\therefore\text{Product is divisble of 2 and 3, therefore divisble by 6}$

I know by substituting in values for n in $(1+3)^{n}-1$ that they all appear divisible by 3, is this a definite rule, is there a proof of this without using induction?

The same goes for $(1+2)^{n}-1$ , how do we know that this is divisble by 2 for all values of n without induction

If we can't use induction to prove those divisbility by 3 and 2, then isn't the question kinda invalid?

Thanks

The $\displaystle 3^n - 1$ is easy, without any tricks like below. $\displaystyle 3^n$ is an odd number, so subtracting 1 from it gives us an even number.

$(1 + 3)^n - 1$ is a bit trickier. Note that when we expand by the binomial theorem:

$(1 + 3)^n - 1 = (1^n + n \cdot 1^{n - 1}3^1 + ~...~ + n \cdot 1^13^{n - 1} + 3^n) - 1$

$\displaystyle = n \cdot 1^{n - 1}3^1 + ~...~ + n \cdot 1^13^{n - 1} + 3^n$
of which you can prove (using the combinatorial coefficients) that every coefficient is divisible by 3.

-Dan

**veileen** · April 9th 2011, 07:30 AM

$(1 + 3)^n - 1 = (1^n + 3 \cdot 1^{n - 1}3^1 + ~...~ + 3 \cdot 1^13^{n - 1} + 3^n) - 1$ - uhm, is not correct.

$(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}\cdot a^{n-k} \cdot b^{k}$ .

**topsquark** · April 9th 2011, 07:58 AM

Originally Posted by veileen

$(1 + 3)^n - 1 = (1^n + 3 \cdot 1^{n - 1}3^1 + ~...~ + 3 \cdot 1^13^{n - 1} + 3^n) - 1$ - uhm, is not correct.

$(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}\cdot a^{n-k} \cdot b^{k}$ .

Whoops! I got carried away with the 3's. Thanks for the catch.

I have fixed it in my post.

-Dan

**Plato** · April 9th 2011, 12:16 PM

Originally Posted by aonin

Hey guys I need help with this question

$\text{prove} <br /> (4^{n}-1)(3^{n}-1) \text{is divisible by 6 for all positive values of n, without Induction}$
and the answer given in the solution to the question is that since
$4^{n}-1=(1+3)^{n}-1 \therefore \text{Divisble by 3}$
$3^{n}-1=(1+2)^{n}-1 \therefore \text{Divisble by 2}$
$\therefore\text{Product is divisble of 2 and 3, therefore divisble by 6}$

Note that $\displaystyle A=4^{n}-1=(1+3)^{n}-1=\sum\limits_{k = 1}^n {\binom{n}{k}\left( 3 \right)^k }$
$\displaystyle B=3^{n}-1=(1+2)^{n}-1=\sum\limits_{k = 1}^n {\binom{n}{k}\left( 2 \right)^k }$

Because the index begins with $k=1$ every term in $A$ is a multiple of 3. Similarly every term is B is even.

Hence every term in the product $AB$ is a multiple of 6.

Thread: Divisibility by 6

LinkBack

Thread Tools

Display

Divisibility by 6

Similar Math Help Forum Discussions

Divisibility 11

Divisibility (gcd) 10

Divisibility (gcd) 9

Divisibility (gcd) 8

Divisibility

Search Tags