A question about the nuances of mathematical induction

49 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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$