Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By Plato

Math Help - Proof by induction - need help understanding this step...

  1. #1
    Newbie
    Joined
    Apr 2014
    From
    United Kingdom
    Posts
    17

    Proof by induction - need help understanding this step...



    Is the question. I've got the mark scheme, but I don't understand it ._.



    How does
    $(k+1)!-1+(k+1)(k+1)!$
    become
    $(k+1)![1+k+1]-1$

    Logically, (k+1)(k+1)! should become the [1+k+1]
    It's not clicking with me - I've been thinking about this for about 20 minutes and it makes no sense to me...
    I'm probably just being retarded...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Proof by induction - need help understanding this step...

    $\\(k+1)!-1+(k+1)(k+1)!=\\(k+1)![1+k+1]-1=\\(k+2)(k+1)!-1=\\(k+2)!-1$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2014
    From
    United States
    Posts
    454
    Thanks
    184

    Re: Proof by induction - need help understanding this step...

    Quote Originally Posted by Bude8 View Post


    Is the question. I've got the mark scheme, but I don't understand it ._.



    How does
    $(k+1)!-1+(k+1)(k+1)!$
    become
    $(k+1)![1+k+1]-1$

    Logically, (k+1)(k+1)! should become the [1+k+1]
    It's not clicking with me - I've been thinking about this for about 20 minutes and it makes no sense to me...
    I'm probably just being retarded...
    Students generally have a lot of trouble with proofs by induction. It does not seem to click intuitively at first.

    One reason is the idiotic way it is presented: the notation used seems to imply that even though n = k also n = k + 1, which is pure nonsense.

    Here is the intuitive idea. Suppose a proposition is true for 1. Suppose as well that if the proposition is true for k, it is also true for k + 1. So it is true for 1, but then it's true for 2, which means it is true for 3, and consequently it is also true for 4, and so on forever and ever and ever, world without end.

    I like to think about the proof this way.

    P(n) is a proposition about the positive integer n.

    Step 1: Prove P(1).

    As a result of step 1, we know that there is at least 1 and maybe more positive integers for which P is true. Choose an arbitrary one of them (call it k).

    So it is not really an assumption that $k\ is\ a\ positive\ integer\ such\ that\ P(k)\ is\ true.$

    We have chosen one of the positive integers for which P(k) is true, and we KNOW that at least one such positive integer exists.

    Step 2: Prove P(k + 1) is true.

    OK Let's look at your problem. The proposition is

    $\displaystyle n \in \mathbb Z^+\ \implies \left(\sum_{i=1}^ni * i!\right) = (n + 1)! - 1.$

    Step 1 is easy.

    $\displaystyle n = 1 \implies \left(\sum_{i=1}^ni * i!\right) = 1 * 1! = 1 * 1 = 1 = 2 - 1 = 2 * 1 - 1 = 2! - 1 = (1 + 1)! - 1 = (n + 1)! - 1.$

    Step 2

    $Let\ k\ be\ an\ arbitrary\ positive\ integer \ such\ that\ \displaystyle \left(\sum_{i=1}^ki * i!\right) = (k + 1)! - 1.$

    A very frequent approach to take is to break down an expression in (k + 1) into two expressions, one in k and the other in k + 1.

    $\displaystyle \left(\sum_{i=1}^{k + 1}i * i!\right) = \left(\sum_{i=1}^ki * i!\right) + (k + 1) * (k + 1)! =$

    $\{(k + 1)! - 1\} + (k + 1) * (k + 1)! = $

    $\{(k + 1)! - 1\} + k * (k + 1)! + 1 * (k + 1)!= $

    $(k + 1)! - 1 + k(k -1)! + (k + 1)!= $

    $k(k + 1)! + 2(k + 1)! - 1 = $

    $(k + 2)(k + 1)! - 1 =$

    $(k + 2)! - 1 =$

    $\{(k + 1) + 1)\}! - 1.$
    Last edited by JeffM; April 15th 2014 at 02:31 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Proof by induction - need help understanding this step...

    Quote Originally Posted by JeffM View Post
    Students generally have a lot of trouble with proofs by induction. It does not seem to click intuitively at first. One reason is the idiotic way it is presented: the notation used seems to imply that even though n = k also n = k + 1, which is pure nonsense.
    It will come as no surprise to you that a mathematician will totally disagree with that.
    I completely understand how it appears idotic to anyone who does not understand what it means to say that the positive integers are well ordered. After all, the induction principle follows from the well ordering axiom.

    Now how is it just for you to make that claim? That may well be the way induction is taught by the mathematics education community, who are by in large not mathematicians. (And it appears explainers such as you define yourself are not either.)

    The logic is impeccable. If each non-empty subset of the positive integers has a first term and the set of the positive integers for which a statement is not true, then there is a first term, $J$, in that subset. If $P(1)$ is true then $J>1$. So $P(J-1)$ must be true.
    But if $P(K)$ being true implies that $P(K+1)$ is true means that $P(J)$ must be true. That is a contradiction. Thus that set for which $P(n)$ is false is empty.
    Last edited by Plato; April 15th 2014 at 04:25 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2014
    From
    United States
    Posts
    454
    Thanks
    184

    Re: Proof by induction - need help understanding this step...

    Quote Originally Posted by Plato View Post
    It will come as no surprise to you that a mathematician will totally disagree with that.
    I completely understand how it appears idotic to anyone who does not understand what it means to say that the positive integers are well ordered. After all, the induction principle follows from the well ordering axiom.

    Now how is it just for you to make that claim? That may well be the way induction is taught by the mathematics education community, who are by in large not mathematicians. (And it appears explainers such as you define yourself are not either.)

    The logic is impeccable. If each non-empty subset of the positive integers has a first term and the set of the positive integers for which a statement is not true, then there is a first term, $J$, in that subset. If $P(1)$ is true then $J>1$. So $P(J-1)$ must be true.
    But if $P(K)$ being true implies that $P(K+1)$ is true means that $P(J)$ must be true. That is a contradiction. Thus that set for which $P(n)$ is false is empty.
    I am not sure what we are disagreeing about. I certainly do not claim to be a mathematician, and I never have been a professional teacher, but I do have some experience trying to teach young people math: in general, they initially find proofs by induction very unintuitive. I blame the way such proofs are introduced to students. Perhaps I am wrong, but you do not say why I am wrong. You seem to think that I am challenging proof by inductions. If I created that impression, I apologize because it was not my intent.

    I see time and time again confusion about what n is supposed to mean in proofs by induction. And why say "assume" there exists k? With step 1 it has been demonstrated that the set of positive integers for which the proposition is true is not empty. No assumption whatsoever is required about the existence of k. And if someone says n = k, then that someone should not also say n is any positive integer or n = k + 1. If n is supposed to represent any positive integer, then k is legitimate only as an arbitrary element of the set of positive integers for which the proposition is true. Step 1 of course has already proved that the relevant set is not empty. Step 2 then shows that the proposition is true of successors.

    $P(1)\ is\ true\ and\ P(k + 1)\ is\ true\ for\ every\ positive\ integer\ for\ which\ P(k)\ is\ true \implies$

    $P(n)\ is\ true\ for\ any\ n\ that\ is\ a\ positive\ integer$ is an argument that can be made intuitively persuasive and the logic of such proofs is then readily comprehensible.

    What is it we are disagreeing about anyway?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2014
    From
    United Kingdom
    Posts
    17

    Re: Proof by induction - need help understanding this step...

    Quote Originally Posted by Plato View Post
    x
    Quote Originally Posted by JeffM View Post

    $\{(k + 1)! - 1\} + (k + 1) * (k + 1)! = $

    $\{(k + 1)! - 1\} + k * (k + 1)! + 1 * (k + 1)!= $

    $(k + 1)! - 1 + k(k -1)! + (k + 1)!= $

    $k(k + 1)! + 2(k + 1)! - 1 = $

    $(k + 2)(k + 1)! - 1 =$

    $(k + 2)! - 1 =$

    $\{(k + 1) + 1)\}! - 1.$

    Sorry guys, I'm probably being incredibly thick but I still don't get it.

    I get where the (k+2)! comes from - multiplying (k+1)! by (k+2), which is the [1+k+1] bit. But I don't get that bit. How do you go from
    (k+1)(k+1)! to [1+k+1]?

    T_T
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Proof by induction - need help understanding this step...

    Quote Originally Posted by Bude8 View Post
    Sorry guys, I'm probably being incredibly thick but I still don't get it.

    I get where the (k+2)! comes from - multiplying (k+1)! by (k+2), which is the [1+k+1] bit. But I don't get that bit. How do you go from
    (k+1)(k+1)! to [1+k+1]?
    Factor out a common factor, $\color{red}{(k+1)!}$

    $\\\color{red}{(k+1)!}-1+(k+1)\color{red}{(k+1)!}=\\\color{red}{(k+1)!}[1+k+1]-1=\\(k+2)\color{red}{(k+1)!}-1=\\(k+2)!-1$
    Thanks from Bude8
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 4th 2013, 08:49 AM
  2. Replies: 2
    Last Post: October 21st 2012, 07:05 PM
  3. Need help understanding a proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 25th 2012, 08:48 PM
  4. Replies: 2
    Last Post: December 29th 2010, 07:38 AM
  5. Replies: 3
    Last Post: April 8th 2008, 05:25 PM

Search Tags


/mathhelpforum @mathhelpforum