Results 1 to 6 of 6

Math Help - Divisibility by 6

  1. #1
    Junior Member
    Joined
    Dec 2010
    Posts
    50

    Divisibility by 6

    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
    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...

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

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by aonin View Post
    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
    Last edited by topsquark; April 9th 2011 at 08:57 AM. Reason: Whoopsie!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    (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}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by veileen View Post
    (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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1

    Wink

    Quote Originally Posted by aonin View Post
    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.
    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: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum