Results 1 to 6 of 6

Math Help - Stuck on Simple Inductive Proof

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Costa Rica
    Posts
    3

    Stuck on Simple Inductive Proof

    Show that for all n \geq 0,
     3^{2n}+4^{n+1} is a mulitple of 5 using an inductive proof.

    I think that I have started this right but I am not sure if it is complete or correct.

     1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5
     2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5,
     p(n+1) = p(n)+3^{2(n+1)}+4^{(n+1)+1}
     = 3^{2n}+4^{n+1}+3^{2n+2}+4^{n+2}
     = 3^{2n}+4^{n+1}+3^{2n}(9)+4^{n+1}(4)
     = 3^{2n}(1+9)+4^{n+1}(1+4) \ by \ factoring
     = 3^{2n}(10)+4^{n+1}(5)

    So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by b.rad View Post
    Show that for all n \geq 0,
     3^{2n}+4^{n+1} is a mulitple of 5 using an inductive proof.

    I think that I have started this right but I am not sure if it is complete or correct.

     1) \ p(0) = 3^{3(0)}+4^{(0)+1}=1+4=5
     2) \ Assume \ p(n)= 3^{2n}+4^{n+1} \ is \ multiple \ of \ 5,
     p(n+1) = p(n)+3^{2(n+1)}+4^{(n+1)+1}
     = 3^{2n}+4^{n+1}+3^{2n+2}+4^{n+2}
     = 3^{2n}+4^{n+1}+3^{2n}(9)+4^{n+1}(4)
     = 3^{2n}(1+9)+4^{n+1}(1+4) \ by \ factoring
     = 3^{2n}(10)+4^{n+1}(5)

    So it appears to me that both terms are indeed multiples of 5; however, I thought the original p(n) would be factored out of the equation. In truth, it just looks a little funny. A little help or clarification would be greatly appreciated.
    Your proof is incorrect - you used the wrong value for P(n+1). Note that P(n+1) is sustained simply by "switching" every n you had in the original expression with n+1. Your proof should have been as follows (skipping the base case):

    If P(n) = 3^{2n}+4^{n+1} then P(n+1) = 3^{2(n+1)} + 4^{(n+1+1)} = 9\cdot 3^{2n} + 4\cdot 4^{n+1} = 4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} \overbrace{=}^{P(n)} 5k + 5\cdot 3^{2n} = 5(k+3^{2n}) for some k \in \mathbb{N}
    Last edited by Defunkt; November 19th 2009 at 11:34 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Costa Rica
    Posts
    3
    Quote Originally Posted by Defunkt View Post
    4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} \overbrace{=}^{P(n)} 5k + 5\cdot 3^{2n} = 5(k+3^{2n}) for some k \in \mathbb{N}
    Thank you for your quick response. I am following well up until here. What just happened? I don't think I'm familiar with this notation.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    The notation meant to illustrate that I used the induction assumption that P(n) is true to get that equality:

    P(n+1): 3^{2(n+1)} + 4^{(n+1+1)} = 9\cdot 3^{2n} + 4\cdot 4^{n+1} = 4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n}

    But since you assumed P(n): 3^{2n}+4^{n+1} = 5k, \ k \in \mathbb{N}, you get:

    P(n+1): 4(3^{2n} + 4^{n+1}) + 5 \cdot 3^{2n} = 4 \cdot 5k + 5 \cdot 3^{2n}  = 5(k+3^{2n}), which is clearly a multiple of 5. And so P(n+1) is true.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I have several suggestions for making inductive proofs. I don't have the weight of education research methodology behind them, so maybe there are more efficient ways of learning induction. However, these recommendations are easy to follow, and they will keep you from 90% of errors, according to my experience.

    1. Distinguish between propositions and numbers. Proposition is a statement that can be either true or false. E.g., "It is raining", "Every even number is divisible by four", "2 + 2 = 5 implies 3 * 0 = 100" (the second is false; the rest are true).

    You cannot add propositions using regular numeric addition. The expression True + False is meaningless. On the other hand, numbers cannot be true or false. Thus, \sum_{i=0}^n i^2 is not a proposition; it's a number.

    2. Know what a property (or predicate, or relation) is. A property is just like proposition, but it requires a number as input. E.g., x=0 can be either true or false depending on x; by itself it is not a proposition. If we denote P(x) to be x = 0, then the proposition P(0) is true and P(1) is false. To remind, P(0) + P(1) is meaningless.

    Notation: I will write P\Leftrightarrow Q to mean that P and Q are equivalent propositions (both are true or both are false). I prefer using = for numbers and \Leftrightarrow for propositions in order to stress the difference. Also, I will write n\mathrel{\vdots} 5 to mean that n is a multiple of 5.

    3. Start the proof by identifying the number property that you need to establish for every natural number. This is usually very easy to do because most statements to prove have the form "For all natural n, P(n)" for some property P. So the first thing is to write what P(n) is. E.g., in your case the proposition to prove is "For all natural n, (3^{2n}+4^{n+1})\mathrel{\vdots}5"; therefore,

    P(n)\Leftrightarrow(3^{2n}+4^{n+1})\mathrel{\vdots  }5

    Make sure to write the general form of P: not P(0) or P(5), but P(n) for a variable n. Also, make sure that P(n) (when n is unbound) is not a proposition; it is a property that becomes a proposition when n is given. Equally important, P(n) is not a number. Thus, writing P(n) = 3^{2n}+4^{n+1} is incorrect.

    4. After this, it's easy. Write and prove the base case P(0) -- a proposition.

    Base case P(0): 3^{2\cdot0}+4^{0+1}\mathrel{\vdots}5

    5. The induction step consists of proving the following proposition: For all n, P(n) implies P(n+1). To prove this, fix an arbitrary n and write the assumption, or induction hypothesis (IH), P(n). In this case,

    IH: Assume P(n), i.e., 3^{2n}+4^{n+1}\mathrel{\vdots}5

    Next write what we need to prove: P(n+1). In this case it is:

    Need to prove P(n+1): 3^{2(n+1)}+4^{(n+1)+1}\mathrel{\vdots}5

    (At the risk of being annoying, I remind that P(n) and P(n+1) are not numbers. Now that we fixed some concrete n, they became propositions.)

    The proof was given in the post above. Instead of P(n)=4(3^{2n}+4^{n+1})+5\cdot 3^{2n}\overbrace{=}^{P(n)} 5k+5\cdot 3^{2n} one should write

    By IH, 3^{2n}+4^{n+1}=5k for some natural number k; therefore
    3^{2(n+1)}+4^{(n+1)+1}=4(3^{2n}+4^{n+1})+5\cdot 3^{2n}=4\cdot 5k+5\cdot 3^{2n}, which is a multiple of 5.

    (Note that I did not write P(n) or P(n+1) in the last two lines because they consists of a chain of equalities of numbers.)

    I hope this helps.

    Evgeny
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    From
    Costa Rica
    Posts
    3

    Thanks

    Thank you for all the help. I understand it completely. Also, thank you for all of the clarifications. It shed a lot of light on several of my recent doubts.

    For others watching this thread I thought it might by helpful to make this step a little more explicit as it confused me a little at first.

    (9)3^{2n}+(4)^{4n+1}

    The coefficient is broken up in order to factor out 3^{2n}+4^{4n+1}.

    (5)3^{2n}+(4)3^{2n}+(4)4^{4n+1} This is like 9A=5A+4A.

    4(3^{2n}+4^{4n+1})+5(3^{2n})
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with Inductive Proof #2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 17th 2009, 04:20 AM
  2. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 02:09 PM
  3. Simple subspace proof using induction: STUCK
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 20th 2009, 02:57 PM
  4. Ugh, another inductive proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 03:56 PM
  5. help...inductive proof???
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum