Results 1 to 3 of 3

Thread: mathematical induction?

  1. #1

    Lightbulb mathematical induction?

    Hi, not sure if this is advanced enough for this sub forum or not. But alas I have a problem, that problem is 'the maths of induction'. I've looked through books and the net, there doesn't seem to be:

    A) Many learning resources on this
    B) Any resource that explains this in a way I can understand

    My lecturer has not seen fit to spend much time on it either. So here are my (3) problems:
    Prove by mathematical induction that
    1+2+3+…..+n = ½n(n+1)
    For all integers n >= 1

    Prove by mathematical induction that
    1+3+5+ ….+ (2n-1) = n2
    For all integers n >= 1

    Prove by mathematical induction that
    12+22+……+n2 = 1/6n(n+1)(2n+1)
    For all integers n >= 1

    Any help (answers and/or explanations) from the wise people of this forum, will be very welcome.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    May 2006
    Lexington, MA (USA)
    Hello, Sarah!

    There are three steps to an Inductive Proof.

    (1)Show that $\displaystyle S(1)$ is true.
    . . That is, that the statement is true for $\displaystyle n = 1$.
    (2) Assume that $\displaystyle S(k)$ is true.
    . . That is, assume the statement is true for $\displaystyle n = k$.
    (3) Proof that $\displaystyle S(k+1)$ is true.
    . . Use $\displaystyle S(k)$ to show that the statement is true for $\displaystyle n = k+1$.

    Prove by Induction that:
    . . $\displaystyle 1 + 2 + 3 + \cdots + n\:=\:\frac{n(n+1)}{2}$
    (1) Verify $\displaystyle S(1)$.
    . . $\displaystyle S(1) \:=\:1 \:=\:\frac{(1)(2)}{2}$ . . . True.

    (2) Assume $\displaystyle S(k)\!:\;\;1 + 2 + 3 \cdots + k \:=\:\frac{k(k+1)}{2}$

    At this point, I write out the statement $\displaystyle S(k+1)$ just to get a look at it.
    This is the statement we want to prove, so it's nice to know what it looks like.

    Replace $\displaystyle k$ with $\displaystyle k+1\!:\;\;1 + 2 + 3 + \cdots + (k+1) \:=\:\frac{(k+1)(k+2)}{2}\quad\Leftarrow\;\text{ S(k+1)}$

    (3) Start with $\displaystyle S(k)\!:\;\;1 + 2 + 3 + \cdots + k \:=\:\frac{k(k+1)}{2}$

    Add $\displaystyle k+1$ to both sides:
    . . $\displaystyle 1 + 2 + 3 + \cdots + k + (k+1) \:=\:\frac{k(k+1)}{2} + (k+1)$

    The left side is the left side of $\displaystyle S(k+1)$.
    We must show that the right side is the right side of $\displaystyle S(k+1)$.

    The right side is: .$\displaystyle \frac{k(k+1)}{2} + (k+1) \:=\:\frac{k(k+1)}{2} + \frac{2(k+1)}{2}$

    . . $\displaystyle = \:\frac{k^2 + k}{2} + \frac{2k + 2}{2}\:=\:\frac{k^2 + 3k + 2}{2} \:=\:\frac{(k+1)(k+2)}{2}$ . . . There!

    We have shown that: .$\displaystyle 1 + 2 + 3 + \cdots + (k+1) \:=\:\frac{(k+1)(k+2)}{2}\quad\Leftarrow\text{ This is S(k+1)}$

    Therefore: .$\displaystyle 1 + 2 + 3 + \cdots + n\:=\:\frac{n(n+1)}{2}$ for all natural numbers $\displaystyle n$.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Nov 2005
    New York City
    Mathematical Induction on the Natual Integers is the 5th Axiom in the Peano Axioms of Arithmetic. Without going into the details of how it can be proved by set theory axioms we will simply state the result. Let $\displaystyle S$ be a subset of $\displaystyle \mathbb{N}$ which satisfies $\displaystyle 1\in S$ and if $\displaystyle k\in S$ then $\displaystyle k+1 \in S$. Conclusion: $\displaystyle S=\mathbb{N}$.

    The general idea is like this.... $\displaystyle 1\in S$ then by the hypothesis $\displaystyle 1+1=2\in S$. But then by the hypothesis $\displaystyle 2+1=3\in S$ and thus on.... Hence we have all the integers.

    I will do the most classical example:
    $\displaystyle 1+2+...+n=\frac{n(n+1)}{2}$ (*).
    We want to show this is true for any natural number $\displaystyle n$. Meaning if $\displaystyle S$ is the set of all natural numbers that satisfy this equation, we want to show $\displaystyle S=\mathbb{N}$. The typical way of doing this is by mathematical induction.
    We need to show two things:
    1)$\displaystyle 1\in S$. Meaning $\displaystyle 1$ satisfies equation (*).
    2$\displaystyle k\in S\to k+1\in S$. Meaning if a natural number satisfies (*) then so does the one after that.

    Again these two conditions are extremely important you cannot have one without the other.

    We check condition #1, certainly,
    $\displaystyle 1=\frac{1(2)}{2}=1$
    Thus, $\displaystyle 1\in S$.
    We check condition #2, let $\displaystyle k$ satisfy (*) that is,
    $\displaystyle 1+2+...+k=\frac{k(k+1)}{2}$
    Add $\displaystyle k+1$ to both sides (you will see why),
    $\displaystyle 1+2+...+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1) (k+2)}{2}$.
    Ah! $\displaystyle k+1$ also satisfies (*).
    Thus, $\displaystyle k\in S\to k+1\in S$.
    Thus, by mathematical induction $\displaystyle S=\mathbb{N}$.

    Typical Approach
    In general people do not do all of what I said above, because it is too lengthy.
    They just show:
    1)$\displaystyle 1$ works.
    2)If $\displaystyle k$ works then $\displaystyle k+1$ works.

    In that case #1 is true because:
    $\displaystyle 1=\frac{1(2)}{2}$.

    And #2 is true because:
    $\displaystyle 1+2+...+k=\frac{k(k+1)}{2}$
    Add $\displaystyle k+1$ to get,
    $\displaystyle 1+2+...+k+(k+1)=\frac{(k+1)(k+2)}{2}$ (algebra omitted).

    And then proof complete. Again this is not a formal mathematical approach but this is usually done to save time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Aug 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Mar 18th 2009, 08:35 AM

Search Tags

/mathhelpforum @mathhelpforum