What does "prove by induction" mean?

Proof by induction means that you proof something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$.

An example:

Proof that $1+2+3+\dots+n = n(n+1)/2$:

• For $n=0$, on the left hand side you've got the empty sum, which by definition is $0$. On the right hand side, you've got $0(0+1)/2=0$. So the euqation is true for $n=0$.

• Assume that the formula is true for $n$. Then we can prove it for $n+1$ as follows:

  By assumption, $1+2+\dots+n+(n+1)=n(n+1)/2 + (n+1)$. But the right hand side is easily calculated to equal $(n+1)((n+1)+1)/2$.

Now since we have proven it for $0$, and for $n+1$ assuming it's true for $n$, we have proven it by induction for all $n$.

The first part is known as induction start, and the second part as induction step.

Now of course you want to know:

Why does it work?

Imagine that you want to know whether it is true for $n=5$. Of course you could just calculate it directly, but assume you've forgotten how to calculate it, and all you remember is that you've proven it for $n=0$ and that if it is true for $n$, then it is true also for $n+1$.

OK, you know it is true for $n=0$.

If it is true for $n=0$, then by the induction step, which you've proven, it is true for $n+1=1$

But if it is true for $n=1$. them by the induction step it is true for $n+1=2$.

But if it is true for $n=2$. them by the induction step it is true for $n+1=3$.

But if it is true for $n=3$. them by the induction step it is true for $n+1=4$.

But if it is true for $n=4$. them by the induction step it is true for $n+1=5$.

Therefore you have proven it for $n=5$.

It is easy to see that this allows you to mechanically formulate a proof for any individual $n$, and thus it is obvious that it must be true for all $n$.

Proof by induction is inherent in the Peano postulates/axioms. If $0$ is in a set $A$ and whenever $n \in A$, the successor $Sn \in A$ then every (non-negative integer) number is in $A$.

This mirrors the base case $0$ and the inductive step from $n$ to $n+1$

Some sets are inductive, and others are not. The natural numbers, non-negative integers, or integers greater than some arbitrary integer $r$ (negative, zero or positive) are all inductive sets.

The fact that Peano had to specify the inductive axiom suggests that it is not quite as obvious as it seems and that your question is non-trivial. There are technical issues of "first order" and "second order" arithmetic in the background. But as in other answers, the principle also seems to be intuitively obvious, and the foundational complexity comes to most people as a surprise.