Proof by induction is a proof technique that allows us to prove that a statement is true for all positive integers. Here’s how it works (Note: $P(n)$ means that the statement is true for the given value $n$):

  1. First, we show that the statement is true for $n = 1$. (i.e. we show $P(1)$ is true.)
  2. Next, we assume that the statement is true for $n = L$, where $L$ is any positive integer (i.e. we assume $P(L)$ is true).
  3. Finally, we show that if the statement is true for $n = L$, then it is also true for $n = L+1$ (i.e. we show that $P(L)$ implies $P(L+1)$).

With induction, we are trying to show two things:

  1. $P(1)$ is true
  2. If $P(L)$ is true, then $P(L+1)$ is true

If we can show these two things, then that means $P(2)$ is true (since $P(1)$ is true and $P(1)$ being true implies $P(1+1) = P(2)$ is true). Then that means $P(3)$ is true (since $P(2)$ being true implies that $P(3)$ is true). Then that means $P(4)$ is true, and so on. By doing this, we have proven that $P(n)$ is true for all positive integer values of $n$.