Results 1 to 9 of 9

Thread: 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
    $\displaystyle t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}$.
    Prove that
    $\displaystyle t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)$
    for all $\displaystyle n \in \mathbb{N}$.

    Incomplete answer (Exercise 1):
    I'm going to prove that
    $\displaystyle t(n + 1) = \binom{2n + 2}{n + 1} = \dfrac{(2n + 2)!}{(n + 1)! * (n + 1)!} \Leftrightarrow \dfrac{4n + 2}{n + 1} * t(n)$.
    Proof:
    $\displaystyle 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)!}$
    $\displaystyle = ...$
    What now? How can I make $\displaystyle (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
    $\displaystyle t(n) \le 4^n$
    for all $\displaystyle n \ge 1$. Hint: Use that $\displaystyle 4n + 2 \le 4(n + 1)$.

    Very incomplete answer (Exercise 2):
    Base step:
    $\displaystyle 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
    9
    Quote Originally Posted by kjey View Post
    [snip]
    Exercise 1:
    For each natural number n, let
    $\displaystyle t(n) = \binom{2n}{n} = \dfrac{(2n)!}{n!*n!}$.

    Prove that
    $\displaystyle t(n + 1) = \dfrac{4n + 2}{n + 1} * t(n)$
    for all $\displaystyle n \in \mathbb{N}$.
    [snip]
    $\displaystyle 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!}$


    $\displaystyle = \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
    9
    Quote Originally Posted by kjey View Post
    [snip]Exercise 2:
    Prove by induction that
    $\displaystyle t(n) \le 4^n$
    for all $\displaystyle n \ge 1$. Hint: Use that $\displaystyle 4n + 2 \le 4(n + 1)$.

    Very incomplete answer (Exercise 2):





    Base step:
    $\displaystyle 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, $\displaystyle 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 $\displaystyle t(k+1) = \dfrac{4k + 2}{k+1}\, t(k)$. Therefore, from the inductive hypothesis:

    $\displaystyle 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 $\displaystyle \frac{(6^n - 1)}{5}$ is an integer for $\displaystyle n \ge 0$.

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

    Prove by induction that $\displaystyle 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; Jun 7th 2008 at 09: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 $\displaystyle \frac{(6^n - 1)}{5}$ is an integer for $\displaystyle n \ge 0$.

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


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

    Prove by induction that $\displaystyle 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 $\displaystyle t(n-1) = n! - 1$ and prove $\displaystyle t(n) = (n + 1)! - 1$

    Now $\displaystyle t(n) = t(n - 1) + n . n! = n! - 1 + n . n! = n!(n+1) - 1 = (n+1)! - 1$

    Algebraic Way:


    $\displaystyle t(n) = t(n - 1) + n . n! =t(n - 1) + (n+1)! - n! $

    $\displaystyle \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!$

    $\displaystyle \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 $\displaystyle 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,410
    Thanks
    1
    $\displaystyle 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: Feb 24th 2010, 10:34 AM
  2. Proof using induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 5th 2009, 08:46 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. Replies: 1
    Last Post: Feb 27th 2009, 09:12 PM
  5. Induction Proof again :(
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 21st 2007, 07:17 AM

Search Tags


/mathhelpforum @mathhelpforum