Results 1 to 9 of 9

Math Help - Proof with algebra, and proof by induction (problems)

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    11

    Proof with algebra, and proof by induction (problems)

    Hi there.

    Soon I have my final exam in Discrete Mathematics, and I'm just working a little bit on proof by induction and refreshing my algebra. There are two exercises that I have some troubles with, and hope that you guys/girls could help me. By the way, sorry if my english is a bit rusty (norwegian).

    Exercise 1:
    For each natural number n, let
    t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}.
    Prove that
    t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)
    for all n \in \mathbb{N}.

    Incomplete answer (Exercise 1):
    I'm going to prove that
    t(n + 1) = \binom{2n + 2}{n + 1} = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} \Leftrightarrow \dfrac{4n + 2}{n + 1} * t(n).
    Proof:
    t(n + 1) = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} = \dfrac{4n + 2}{n + 1} * t(n) = \dfrac{4n + 2}{(n + 1)} * \dfrac{(2n)!}{n! * n!} = \dfrac{(4n + 2) * (2n)!}{(n + 1)! * (n + 1)!}
    = ...
    What now? How can I make (4n + 2) * (2n)! = (2n + 2)! ? Maybe I have done something wrong in the process, or is it my algebra skills?

    Exercise 2:
    Prove by induction that
    t(n) \le 4^n
    for all n \ge 1. Hint: Use that 4n + 2 \le 4(n + 1).

    Very incomplete answer (Exercise 2):
    Base step:
    t(1) = 2 \le 4^1 = 4.
    The claim is true for n = 1.

    Inductive step:
    ...

    Hehe, I'm stuck right here... Hope someone can help me =D

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by kjey View Post
    [snip]
    Exercise 1:
    For each natural number n, let
    t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}.

    Prove that
    t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)
    for all n \in \mathbb{N}.
    [snip]
    t(n+1) = \dfrac{(2[n+1])!}{(n+1)! \, (n+1)!} = \dfrac{(2n+2)!}{(n+1) n! \, (n+1) n!} = \dfrac{(2n+2) (2n + 1) (2n)!}{(n+1) n! \, (n+1) n!}


     = \dfrac{(2n+2)(2n+1)}{(n+1)^2} ~ \dfrac{(2n)!}{n! \, n!} = \dfrac{2(n+1)(2n+1)}{(n+1)^2} \, t(n) = \dfrac{2(2n+1)}{n+1} \, t(n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by kjey View Post
    [snip]Exercise 2:
    Prove by induction that
    t(n) \le 4^n
    for all n \ge 1. Hint: Use that 4n + 2 \le 4(n + 1).

    Very incomplete answer (Exercise 2):





    Base step:
    t(1) = 2 \le 4^1 = 4.
    The claim is true for n = 1.
    [snip]
    Step 2: Assume true for n = k > 1, that is, t(k) \leq 4^k (inductive hypothesis).

    Step 3: Show that it follows from step 2 that it's true for n = k + 1.

    It follows from Exercise 1 that t(k+1) = \dfrac{4k + 2}{k+1}\, t(k). Therefore, from the inductive hypothesis:

    t(k+1) \leq \dfrac{4k + 2}{k+1}\, 4^k \leq \dfrac{4k + {\color{red}4}}{k+1}\, 4^k = \dfrac{4(k + 1)}{k+1}\, 4^k = 4^{k+1}.

    Therefore etc. etc.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2008
    Posts
    11
    Thank you very much! Very helpfull
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    11
    One (two?) more problem(s):

    Exercise 3:
    I think I have solved this one, but I want a confirmation that it is correct.

    Prove that \frac{(6^n - 1)}{5} is an integer for n \ge 0.

    Answer (Exercise 3):
    1. Let t(n) = \frac{(6^n - 1)}{5}.
    2. t(0) = \frac{(6^0 - 1)}{5} = 0, the claim is true for n = 0.
    3. I assume that the claim is true for some arbitrary n = k.
    4. The formula is true if (6^k - 1) is a factor of 5, hence (6^k - 1) = 5i when i is an integer (this is the inductive hypothesis).
    5. t(k + 1) = \frac{(6^{k+1} - 1)}{5} = \frac{6 * 6^k - 1}{5} = \frac{6 * (6^k -1) + 5}{5} = \frac{6 * 5i + 5}{5}.
    6. 6 * 5i + 5 is a factor of 5, therefor the claim is proven (I hope...).
    Exercise 4:
    t(1) = 1, t(n) = t(n - 1) + n * n!.

    Prove by induction that t(n) = (n + 1)! - 1.

    I understand how I can prove this, but I dont see how I can use algebra-manipulation to do this. Hope someone can help me!
    Last edited by kjey; June 7th 2008 at 10:10 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by kjey View Post
    One (two?) more problem(s):

    Exercise 3:
    I think I have solved this one, but I want a confirmation that it is correct.

    Prove that \frac{(6^n - 1)}{5} is an integer for n \ge 0.

    Answer (Exercise 3):
    1. Let t(n) = \frac{(6^n - 1)}{5}.
    2. t(0) = \frac{(6^0 - 1)}{5} = 0, the claim is true for n = 0.
    3. I assume that the claim is true for some arbitrary n = k.
    4. The formula is true if (6^k - 1) is a factor of 5, hence (6^k - 1) = 5i when i is an integer (this is the inductive hypothesis).
    5. t(k + 1) = \frac{(6^{k+1} - 1)}{5} = \frac{6 * 6^k - 1}{5} = \frac{6 * (6^k -1) + 5}{5} = \frac{6 * 5i + 5}{5}.
    6. \frac{6 * 5i + 5}{5} is a factor of 5, therefor the claim is proven (I hope...).
    Perrrrrfect


    Exercise 4:
    t(1) = 1, t(n) = t(n - 1) + n * n!.

    Prove by induction that t(n) = (n + 1)! - 1.

    I understand how I can prove this, but I dont see how I can use algebra-manipulation to do this. Hope someone can help me!

    Induction way:


    t(2) is evident. Assume the result for n - 1 and prove for n.

    That is assume t(n-1) = n! - 1 and prove t(n) = (n + 1)! - 1

    Now t(n) = t(n - 1) + n . n! = n! - 1 + n . n! = n!(n+1) - 1 = (n+1)! - 1

    Algebraic Way:


     t(n) = t(n - 1) + n . n! =t(n - 1) + (n+1)! - n!

    \Rightarrow t(m) - t(m - 1) = (m+1)! - m! \Rightarrow \sum_{m=2}^{m=n}t(m) - t(m - 1) = \sum_{m=2}^{m=n} (m+1)! - m!

    \Rightarrow t(n) - t(1) = (n+1)! - 2! \Rightarrow t(n) = (n+1)! - 2 + t(1) \Rightarrow t(n) = (n + 1)! - 1
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2008
    Posts
    11
    Hmmm... can you explain how n! - 1 + n * n! = n!(n+1) - 1. I'm not a "pro" in algebra
    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    n! - 1 + n \cdot n! \: \: = \: \: n! + n\cdot n! - 1 \: \: = \: \: n!(1+ n) - 1 \: \: = \: \: n!(n+1) - 1

    Basically factored out n! from (n! + nn!).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2008
    Posts
    11
    Thanks I should have understand it in the first place

    Anyway, my teacher (professor) said that one task at the exam could be to prove a linear recurrence equation (at(n) + bt(n - 1) + ct(n - 2) = 0). There are no examples in the book, and he have never showed it to us. Could some one give me a task that I can solve? I know how to solve the equation, but I have never proved it...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help with the algebra in an induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 24th 2010, 11:34 AM
  2. Proof using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 5th 2009, 09:46 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. Replies: 1
    Last Post: February 27th 2009, 10:12 PM
  5. Induction Proof again :(
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 21st 2007, 08:17 AM

Search Tags


/mathhelpforum @mathhelpforum