Results 1 to 3 of 3

Math Help - Induction Proof

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    4

    Induction Proof

    Been having a few problems understanding the logic (step by step process) of Induction. If someone could help me out on the following, it would be greatly appreciated!

    Prove using induction:

    1 + 3 + 5 + ... + (2n-1) = (n+1)^2

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    32
    To understand the logic of induction, I will just quote Wikipedia:

    "It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one."

    So let's do this with your problem:

    Our conjecture (called P_{n}) is 1+3+5+...+(2n-1)=n^2

    1)First, let's check if the first term (when n = 1) is true:

    P_{1} is 2(1)-1 = 1^2

    1=1\therefore P_{1} is true.

    2)Now, by letting n = k, we consider our conjecture for P_{k}:

    1+3+5+...+(2k-1)=\color{blue}k^2

    3)Then, by letting n = (k + 1), we consider the next case ( P_{k+1})

    \color{blue}1+3+5+...+(2k-1)\color{black}+(2[k+1]-1) = (k+1)^2

    Notice how the blue part is actually P_{k}. Thus, we may replace that series by the summation formula (all blue expressions are equal to each other):

    \color{blue}k^2\color{black}+2k+1=(k+1)^2

    k^2+2k+1=k^2+2k+1

    \therefore P_{k+1} is true

    4)So, P_{k} being true necessarily implies that P_{k+1} must also be true. Knowing that P_{1} is true, we may use this (by letting k = 1), to conclude that P_{2} is also true, and then (by replacing k = 2) conclude that P_{3} is also true, repating this processes ad infinitum.

    \therefore P_{n} is true and the conjecture is proven.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    21
    Wow, Referos, thank you. I've been struggling with inductive proofs for weeks and the way you illustrated the concept, something clicked this time.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 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. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum