Results 1 to 9 of 9

Math Help - few problems on proving using induction

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    22

    few problems on proving using induction

    1) So I need to prove that (1+x)^n <= 1 + xn (x>= -1)

    I did  (1+x)^n+1 >= 1+x(n+1) ;then I just don't know where to go.
    Then There are 2 sequence ones that I don't even know where to begin

    a) Let Fn be the n-th term of the Fibonacci Sequence 1, 1, 2, 3, 5, 8,.. Defined by the rule:
    F(n+2) = F(n) + F(n+1) [ Fn is F sub n]
    prove by induction that F1+F2 +....+Fn  <=2^(n+1)


    b) The sequence a1, a2, a3, a4, ... an,... [again a sub n]
    of positive integers defined by the rule:
    a1 =1 a(n+1) = 3an (3 times a sub n) ( n = 1, 2,3,..) Prove that an = 3 ^(n-1) for n= 1,2,...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Induction

    Hello meg0529
    Quote Originally Posted by meg0529 View Post
    1) So I need to prove that (1+x)^n \color{red}<=\color{black} 1 + xn (x>= -1)

    I did  (1+x)^n+1 >= 1+x(n+1) ;then I just don't know where to go.
    You mean (1+x)^n >= 1 + xn (x>= -1), of course.

    So let P(n) be the propositional function (1+x)^n >= 1 + xn (x>= -1)

    Then, provided (1+x) \ge 0, we can multiply both sides by (1+x). So for x\ge -1:

    P(n) \Rightarrow (1+x)^{n+1} \ge (1+x)(1+nx)

    \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x + nx^2

    \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x, since n>0 \Rightarrow nx^2 \ge 0

    \Rightarrow P(n+1)

    Can you complete it now?

    (I must sign off now - I'll look at the others later, if no-one else does first.)

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Induction on a Fibonacci sequence

    Hello again meg0529
    Quote Originally Posted by meg0529 View Post
    a) Let Fn be the n-th term of the Fibonacci Sequence 1, 1, 2, 3, 5, 8,.. Defined by the rule:
    F(n+2) = F(n) + F(n+1) [ Fn is F sub n]
    prove by induction that F1+F2 +....+Fn  <=2^(n+1)
    In fact, we can prove the strict inequality \sum_{i=1}^nF_i < 2^{n+1}.

    This is a little bit different from the usual induction proof. Notice that when we add the next term, F_{n+1}, we would need to prove that the new sum < 2^{n+2}= 2^{n+1} + 2^{n+1}. So if we can prove that F_{n+1} < 2^{n+1}, we're there. We do this in, again, a slightly unusual way, by assuming that we have two consecutive values of n for which it's true.

    So let P(n) be the propositional function: F_n < 2^n

    Then (P(n) \wedge P(n-1)) \Rightarrow F_n + F_{n-1}< 2^n+2^{n-1} = 2^n(1 + \tfrac{1}{2}) (Do you understand the notation I'm using here?)

    \Rightarrow F_{n+1} < 2^{n+1}

    P(1) is F_1 < 2^1, which is true; P(2) is F_2 < 2^2, which is also true. So P(n) is true \forall n \ge 1.

    \Rightarrow \sum_{i=1}^nF_i < \sum_{i=1}^n2^i = \frac{2(2^n-1)}{2-1} =2^{n+1} - 2 (Do you understand this bit? It's a GP, first term 2, common ratio 2.)

    \Rightarrow \sum_{i=1}^nF_i < 2^{n+1}

    b) The sequence a1, a2, a3, a4, ... an,... [again a sub n]
    of positive integers defined by the rule:
    a1 =1 a(n+1) = 3an (3 times a sub n) ( n = 1, 2,3,..) Prove that an = 3 ^(n-1) for n= 1,2,...
    Have you tried this question? If you can't to it, then you're really not understanding anything about induction at all. The a_n here are simply the terms of a GP.

    Just start with:

    Let P(n) be the statement (propositional function) involving n: a_n = 3^{n-1}, and then use the formula for a_{n+1} to show that P(n) \Rightarrow P(n+1). Then check that P(1) is true, and you're done.

    Show us your attempt if you'd like us to check it for you.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    22
    Thanks a lot Grandpa, I'll work them out and see how it goes. My professor has done a real bad job of explaining induction and I'm working off of the worst textbook ever, so I'm quite shakey on this stuff. I'll work em out and post what what I get.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    22
    \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x, since n>0 \Rightarrow nx^2 \ge 0

    I don't fully understand why we can drop the nx^2...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello meg0529
    Quote Originally Posted by meg0529 View Post
    \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x, since n>0 \Rightarrow nx^2 \ge 0

    I don't fully understand why we can drop the nx^2...
    x^2 \ge 0 for all values of x. So if n > 0, nx^2 \ge 0. Therefore 1+(n+1)x + nx^2 \ge 1+(n+1)x.

    OK?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2009
    Posts
    22
    I see the inequality, I just don't know how to interpret it. If 1 + x(n+1)+nx^2 was less than 1+x(n+1), we wouldn't need to worry for as long as we can prove that (1+x)^(n+1) is >= 1+x(n+1). but in this case 1 + x(n+1)+nx^2 is larger than 1+x(n+1)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello meg0529
    Quote Originally Posted by meg0529 View Post
    I see the inequality, I just don't know how to interpret it. If 1 + x(n+1)+nx^2
    Quote Originally Posted by meg0529 View Post
    was less than 1+x(n+1)???, we wouldn't need to worry for as long as we can prove that (1+x)^(n+1) is >= 1+x(n+1). but in this case 1 + x(n+1)+nx^2 is larger than 1+x(n+1)
    What's the problem here? We have A \ge B and B \ge C. So surely A \ge C. I repeat: what's the problem?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2009
    Posts
    22

    Red face

    OH! Ok I see it, I was looking at it all wrong. Thank you so much for your patience, and answers!

    Now I'll get working on those series ones >.<
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving an inequation with induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 9th 2011, 11:17 AM
  2. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 01:13 PM
  3. Proving a statement by Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2011, 02:57 AM
  4. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 04:50 PM
  5. Need help proving mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 29th 2009, 08:16 AM

Search Tags


/mathhelpforum @mathhelpforum