Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By MathoMan

Math Help - Proof by induction inequality

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    28

    Proof by induction inequality

    Prove \sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n} for all n \epsilon \mathbb{N}

    Proof: i) Show P(1) holds.

    LHS = \sum_{i=1}^1 \frac{1}{i^2} = \frac{1}{1} = 1
    RHS = 2 - \frac{1}{1} = 2 - 1 = 1

    LHS  \le RHS, thus, P(1) holds.

    ii) Assume P(k) holds for some k \epsilon \mathbb{N}
    That is, assume \sum_{i = 1}^k \frac{1}{i^2} \le 2 - \frac{1}{k}.

    To show: P(k + 1):  \sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}

    Then  \sum_{i=1}^{k+1} \frac{1}{i^2} = \left( \sum_{i=1}^{k}  \frac{1}{i^2} \right) + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} +  \frac{1}{(k+1)^2}

    Not sure what to do next. In my next step, I said 2 - \frac{1}{k} +  \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{k+1}. But I'm not sure if this is the right path to take.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,506
    Thanks
    1402

    Re: Proof by induction inequality

    Quote Originally Posted by deezy View Post
    Prove \sum_{i=1}^n \frac{1}{i^2} \le 2 - \frac{1}{n} for all n \epsilon \mathbb{N}

    Proof: i) Show P(1) holds.

    LHS = \sum_{i=1}^1 \frac{1}{i^2} = \frac{1}{1} = 1
    RHS = 2 - \frac{1}{1} = 2 - 1 = 1

    LHS  \le RHS, thus, P(1) holds.

    ii) Assume P(k) holds for some k \epsilon \mathbb{N}
    That is, assume \sum_{i = 1}^k \frac{1}{i^2} \le 2 - \frac{1}{k}.

    To show: P(k + 1):  \sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}

    Then  \sum_{i=1}^{k+1} \frac{1}{i^2} = \left( \sum_{i=1}^{k}  \frac{1}{i^2} \right) + \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} +  \frac{1}{(k+1)^2}

    Not sure what to do next. In my next step, I said 2 - \frac{1}{k} +  \frac{1}{(k+1)^2} \le 2 - \frac{1}{k} + \frac{1}{k+1}. But I'm not sure if this is the right path to take.
    What you have done is fine, but you need to state why that inequality is true, the reason being that \displaystyle \begin{align*} (k + 1)^2 > k + 1 \end{align*} for all \displaystyle \begin{align*} k > 1 \end{align*}. Then you can say \displaystyle \begin{align*} 2 - \frac{1}{k} + \frac{1}{k + 1} < 2 + \frac{1}{k + 1} \end{align*}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2011
    Posts
    28

    Re: Proof by induction inequality

    But I'm not sure how I can use 2 + \frac{1}{k + 1} since it isn't less than 2 - \frac{1}{k + 1}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13

    Re: Proof by induction inequality

    2-\frac{1}{n}+\frac{1}{(n+1)^2}=2-\left(\frac{1}{n}-\frac{1}{(n+1)^2} \right)=2-\frac{n^2+n+1}{n(n+1)^2}

    Now you just have to prove that \frac{n^2+n+1}{n(n+1)^2} is greater than or equal to \frac{1}{n+1},
    because that would give you the result 2-\frac{n^2+n+1}{n(n+1)^2}\leq 2-\frac{1}{n+1}.

    But needed inequality holds since
    \frac{n^2+n+1}{n(n+1)^2}& =\frac{n(n+1)+1}{n(n+1)^2}=\frac{n(n+1)}{n(n+1)^2}  +\frac{1}{n(n+1)^2}= \\ &=\frac{1}{n+1}+\frac{1}{n(n+1)^2}\geq \frac{1}{n+1}.
    Thanks from deezy
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 8th 2011, 10:19 AM
  2. Induction proof concerning a finite sum inequality
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 11th 2011, 08:44 AM
  3. Proof of mathematical induction inequality
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 15th 2010, 03:34 PM
  4. Proof of inequality by transfinite induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 10th 2010, 10:17 AM
  5. Induction Proof (Inequality) SIMPLE!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 3rd 2010, 02:58 AM

Search Tags


/mathhelpforum @mathhelpforum