Results 1 to 9 of 9

Thread: 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 $\displaystyle (1+x)^n <= 1 + xn (x>= -1)$

    I did $\displaystyle (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 $\displaystyle <=$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
    Thanks
    1

    Induction

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

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

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

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

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

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

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

    $\displaystyle \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
    Thanks
    1

    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 $\displaystyle <=$2^(n+1)
    In fact, we can prove the strict inequality $\displaystyle \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, $\displaystyle F_{n+1}$, we would need to prove that the new sum < $\displaystyle 2^{n+2}= 2^{n+1} + 2^{n+1}$. So if we can prove that $\displaystyle 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 $\displaystyle n$ for which it's true.

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

    Then $\displaystyle (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?)

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

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

    $\displaystyle \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.)

    $\displaystyle \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 $\displaystyle a_n$ here are simply the terms of a GP.

    Just start with:

    Let $\displaystyle P(n)$ be the statement (propositional function) involving $\displaystyle n$: $\displaystyle a_n = 3^{n-1}$, and then use the formula for $\displaystyle a_{n+1}$ to show that $\displaystyle P(n) \Rightarrow P(n+1)$. Then check that $\displaystyle 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
    $\displaystyle \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $\displaystyle 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
    Thanks
    1
    Hello meg0529
    Quote Originally Posted by meg0529 View Post
    $\displaystyle \Rightarrow (1+x)^{n+1} \ge 1 + (n+1)x$, since $\displaystyle n>0 \Rightarrow nx^2 \ge 0$

    I don't fully understand why we can drop the nx^2...
    $\displaystyle x^2 \ge 0$ for all values of $\displaystyle x$. So if $\displaystyle n > 0$, $\displaystyle nx^2 \ge 0$. Therefore $\displaystyle 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
    Thanks
    1
    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 $\displaystyle A \ge B$ and $\displaystyle B \ge C$. So surely $\displaystyle 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: Dec 9th 2011, 11:17 AM
  2. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 10th 2011, 01:13 PM
  3. Proving a statement by Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 20th 2011, 02:57 AM
  4. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 30th 2009, 04:50 PM
  5. Need help proving mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 29th 2009, 08:16 AM

Search Tags


/mathhelpforum @mathhelpforum