1

Say I am trying to prove the statement $$1\cdot1! + 2\cdot 2! + \cdots + n \cdot n! = (n+1)!-1$$ by mathematical induction. I start by declaring that $P(n)$ is the statement given by $$1\cdot1! + 2\cdot 2! + \cdots + n \cdot n! = (n+1)!-1.$$ Now, I want to show that the base case, $P(1)$ is true. In other words, I want to show that $$1\cdot 1! = (1+1)!-1$$ is true. "Doing math" on both sides shows that $1=1$, a true statement. Thus, I conclude that $P(1)$ is a true statement.

However, I was told by my professor that I cannot simply plug $1$ into both sides of the equation from $P(n)$ since this starts by assuming that $P(1)$ is true. I am confused by this. I never actually asserted the true value of $P(1)$. Yes, I plugged $1$ into $P(n)$, but only in order to show that $P(n)$ holds for $n=1$. Is what I did incorrect? And if so, how would I correctly show this base case?

playitright
  • 631
  • 3
    You need to know that the "doing math" you did is reversible; strictly speaking you should write down a proof of $P(1)$ by starting from $1 = 1$ and reversing all the steps, although it suffices to explicitly state that all of the steps were reversible. – Qiaochu Yuan Oct 06 '19 at 21:56
  • 2
    Technically, you should plug 1 into the left-hand side of the equation, and plug 1 into the right-hand side of the equation, then check whether they're equal. This is basically what you did; your professor is just being nit-picky. – Dzoooks Oct 06 '19 at 21:56
  • 1
    Both of these explanations make sense. Thank you for the clarification! – playitright Oct 06 '19 at 21:59

1 Answers1

4

I have seen many students get into trouble going about it this way.

In particular, I have seen many proofs that end with something to the effect of $1=1$ ... followed by a triumphant QED!

But the problem is that of course $1=1$ ... showing that $1=1$ therefore does not mean anything at all.

Even more problematically, with this method you start with $LHS=RHS$, and end with $1=1$, while what you really need to end with is $LHS=RHS$

For example, suppose I need to show that $LHS=RHS$.

Now, your method of starting with the $LHS=RHS$, and ending up with $1=1$ could go something like this:

$1. LHS = RHS$

$2. LHS*0 = RHS*0$ (from 1)

$3. 0=0$ (from 2)

$4. 0+1=0+1$ (from 3)

$5. 1=1$ (from 4)

QED!

OK, I think you see the problem, and while this is not what you did, I have seen much more subtle ways in which students end up doing something like this ... and therefore end up showing nothing of interest at all!

The first comment are therefore exactly on track: you need to be able to reverse the steps, so that in fact you can derive that $LHS=RHS$. Or, as the second comment points out: you can start with $LHS$, and then 'do math' to end up with $RHS$

Bram28
  • 100,612
  • 6
  • 70
  • 118