Results 1 to 5 of 5

Math Help - Induction Proof

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    51

    Induction Proof

    Hi all,

    This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

    "Prove that 3^n - 1 is a multiple of 4 for all even numbers n"

    Any help is appreciated. Thanks,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Rafael Almeida View Post
    Hi all,

    This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?
    "Prove that 3^n - 1 is a multiple of 4 for all even numbers n"
    Any help is appreciated. Thanks,
    outline:

    clearly the claim is true for n = 0.

    assume it is true for any positive even integer n, that is, 3^n - 1 = 4k for some integer k.

    then, we have 3^{n + 2} - 1 = 3^2 \cdot 3^n - 1 = 3^2 \cdot 3^n - 3^2 + 8 = ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Rafael Almeida View Post
    Hi all,

    This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?

    "Prove that 3^n - 1 is a multiple of 4 for all even numbers n"

    Any help is appreciated. Thanks,
    3^{2n} - 1 = 9^n - 1 = (9-1)(9^{n-1}+9^{n-2}+ ... + 9 + 1)
    We see this number is even (pun!) divisible by 8.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2008
    Posts
    4

    Smile

    Quote Originally Posted by Rafael Almeida View Post
    Hi all,

    This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?
    "Prove that 3^n - 1 is a multiple of 4 for all even numbers n"
    Any help is appreciated. Thanks,
    Hey,

    You get my first post ever . I thought about it and I have a different approach which might be easier to understand.

    T(n) = 3^n - 1

    The task is proving that its a multiple of 4 for all even numbered n values.
    2n is always even, and 4k is always a multiple of 4. (k is any other number...it's just for show in my opinion).

    so it becomes:

    T(n) = 3^n - 1 = 4k

    make the left look somewhat like the right:

    T(any even) = T(2n) = 3^(2n) - 1 = 3*3*3^n - 1.

    We have odd * odd * (odd)^n - 1.

    can we find a property about odd number multiplication? we might be able to...

    Every odd number can be represented by 2p+1, where p is any number. In short, multiply any number by 2 (making it even) and add 1 (making it odd).

    (2p+1)(2p+1) = (2p)^2 + 4p + 1

    (2p)^2 = 4 * p^2 = 2 * 2 * p^2 ===> even
    4 * p = 2 * 2 * p =====> even
    1 ====> odd

    prove even + even is always even
    2p + 2j = 2 * (p+j) ===> 2 * some number ==> even

    going backward to where the smiley is, we have:

    odd * odd * odd^n - 1 = odd - 1 = even.

    The explanation is long but depending on the person looking at it they would understand it right away or not...so we can see that we met the condition. The nice thing here is that the person didn't say the following:

    3^n - 1 is an integer multiple of 4 where n is even and n > 1...so we can accept fraction * 4....

    for ex, take n=3:
    27-1=26 (not an integer multiple of 4 but it works)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Last_Singularity's Avatar
    Joined
    Dec 2008
    Posts
    157
    Quote Originally Posted by Rafael Almeida View Post
    Hi all,

    This one was supposed to be easy, but I keep getting stuck in it in the inductive case... thouhgts?
    "Prove that 3^n - 1 is a multiple of 4 for all even numbers n"
    Any help is appreciated. Thanks,
    Perhaps this will be more clear.

    To simplify this problem, we can substitute n=2k. Thus picking any k \in N ensures that n is even. The problem then becomes

    3^{2k} - 1 = (3^2)^k - 1 = 9^k - 1 is a multiple of 4 for all integers k.

    Step 1: Check case base: 9^k - 1 such that k=0 is 9-1=8, which is indeed a multiple of 4.

    Step 2: Assume that 9^k - 1 modulo 4 is 0. This is the claim for case where we have k.

    Step 3 (induction step): Check that if 9^k - 1 modulo 4 is 0, then 9^{k+1} - 1 is also 0 modulo 4. This will show that if k works, then so will k+1. We do this as follows:

    9^{k+1} - 1 = 9(9^k) -1 = 9(9^k-1) + 8

    Thus, if 9^k - 1 is 0 modulo 4, then multiplying it by 9 and adding 8 is also 0 modulo 4.

    The proof is then complete.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum