Results 1 to 6 of 6

Thread: Divisibility by 6

  1. #1
    Junior Member
    Joined
    Dec 2010
    Posts
    50

    Divisibility by 6

    Hey guys I need help with this question

    $\displaystyle \text{prove}
    (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

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

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

    I know by substituting in values for n in $\displaystyle (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$\displaystyle (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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    1.
    I guess you don't know Newton's generalized binomial theorem...

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

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

    2.
    $\displaystyle 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:
    $\displaystyle 4^n-1=(4-1)(4^{n-1}+4^{n-2}+...+4+1)=3(4^{n-1}+4^{n-2}+...+4+1)$
    $\displaystyle 3^n-1=(3-1)(3^{n-1}+3^{n-2}+...+3+1)=2(3^{n-1}+3^{n-2}+...+3+1)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,129
    Thanks
    722
    Awards
    1
    Quote Originally Posted by aonin View Post
    Hey guys I need help with this question

    $\displaystyle \text{prove}
    (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

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

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

    I know by substituting in values for n in $\displaystyle (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$\displaystyle (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 $\displaystyle \displaystle 3^n - 1$ is easy, without any tricks like below. $\displaystyle \displaystyle 3^n$ is an odd number, so subtracting 1 from it gives us an even number.

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

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

    $\displaystyle \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
    Last edited by topsquark; Apr 9th 2011 at 07:57 AM. Reason: Whoopsie!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    $\displaystyle (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.

    $\displaystyle (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}\cdot a^{n-k} \cdot b^{k}$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,129
    Thanks
    722
    Awards
    1
    Quote Originally Posted by veileen View Post
    $\displaystyle (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.

    $\displaystyle (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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,743
    Thanks
    2814
    Awards
    1

    Wink

    Quote Originally Posted by aonin View Post
    Hey guys I need help with this question

    $\displaystyle \text{prove}
    (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
    $\displaystyle 4^{n}-1=(1+3)^{n}-1 \therefore \text{Divisble by 3}$
    $\displaystyle 3^{n}-1=(1+2)^{n}-1 \therefore \text{Divisble by 2}$
    $\displaystyle \therefore\text{Product is divisble of 2 and 3, therefore divisble by 6}$
    Note that $\displaystyle \displaystyle A=4^{n}-1=(1+3)^{n}-1=\sum\limits_{k = 1}^n {\binom{n}{k}\left( 3 \right)^k } $
    $\displaystyle \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 $\displaystyle k=1$ every term in $\displaystyle A$ is a multiple of 3. Similarly every term is B is even.

    Hence every term in the product $\displaystyle AB$ is a multiple of 6.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum