logic - Mathematical induction question: why can we "assume $P(k)$ holds"?

So I see that the process for proof by induction is the following (using the following statement for sake of example: $P(n)$ is the formula for the sum of natural numbers $\leq n$: $0 + 1 + \cdots +n = (n(n+1))/2$ )

1. Show that the base case is trivially true: $P(0)$: let $n = 0$. Then $0 = (0(0+1))/2$, which is true.


2. Show that if $P(k)$ holds then $P(k+1)$ also holds. Assume $P(k)$ holds for some unspecified value of $k$. It must be then shown that $P(k+1)$ holds.

This is the part I don't get: 'Assume $P(k)$ holds'

We are just assuming something is true and then 'proving' that something else is true based on that assumption. But we never proved the assumption itself is true so it doesnt seem to hold up to me. Oviously proof by induction works so am I viewing the process incorrectly?

Answer

The "inductive step" is a proof of an implication: $$\mathbf{if}\ P(k),\ \mathbf{then}\ P(k+1).$$ So we are trying to prove an implication.

When proving an implication, instead of proving the implication, we usually assume the antecedent (the clause after "if" and before "then"), and then use that to prove the consequent (the clause after "then"). There are several reasons why this is reasonable, and one reason why it is valid.

Reasonable:

1. 
   

   An implication, $P\to Q$, is false only in the case where $P$ is true but $Q$ is false. In any other combination of "truth values", the implication is true. So in order to show that $P\to Q$ is valid (always true), it is enough to consider the case when $P$ is already true: if $P$ is false, then the implication will be true regardless of what $Q$ is.

   
   


2. 
   

   More informally: in proving $P\to Q$, we can say: "if $P$ is false, then it doesn't matter what happens to $Q$, and we are done; if $P$ is true, then..." and proceed from there.

   
   

Why is it a valid method of proof?

There is something called the Deduction Theorem. What it says is that if, from the assumption that $P$ is true, you can produce a valid proof that shows that $Q$ is true, then there is a recipe that will take that proof and transform it into a valid proof that $P\to Q$ is true. And, conversely, if you can produce a valid proof that $P\to Q$ is true, then from the assumption that $P$ is true you can produce a proof that shows that $Q$ is true.

The real interesting part of the Deduction Theorem is the first part, though: that if you can produce a proof of $Q$ from the assumption that $P$ is true, then you can produce a proof of $P\to Q$ without assuming anything about $P$ (or about $Q$). It justifies the informal argument given above.

That's why, in mathematics, whenever we are trying to prove an implication, we always assume the antecedent is already true: the Deduction Theorem tells us that this is a valid method of proving the implication.