Induction is by far the most powerful and commonly-used proof technique in
Discrete Mathematics and Computer Science.  In fact, the use of induction
is a defining characteristic of \emph{discrete} ---as opposed to
\emph{continuous} ---Mathematics.
%
To understand how it works, suppose there is a professor who brings
to class a bottomless bag of assorted miniature candy bars.  She offers to
share the candy in the following way.  First, she lines the students up in
order.  Now she states two rules:

\begin{enumerate}
\item The student at the beginning of the line gets a candy bar.
\item If a student gets candy bar, then the following student in line
  also gets a candy bar, for every student in the line.
\end{enumerate}
%
Let's number the students by their order in line, starting the count with
0, as usual in Computer Science.  Now we can understand the second rule as
a short description of a whole sequence of statements:
%
\begin{itemize}
\item If student 0 gets a candy bar, then student 1 also gets one.
\item If student 1 gets a candy bar, then student 2 also gets one.
\item If student 2 gets a candy bar, then student 3 also gets one.

\hspace{1.2in} \vdots
\end{itemize}
%
Of course this sequence has a more concise mathematical description:
\begin{quote}
  If student $n$ gets a candy bar, then student $n+1$ gets a
  candy bar, for all nonnegative integers $n$.
\end{quote}
So suppose you are student 17.  By these rules, are you entitled to a
miniature candy bar?  Well, student 0 gets a candy bar by the first rule.
Therefore, by the second rule, student 1 also gets one, which means
student 2 gets one, which means student 3 gets one as well, and so on.  By
17 applications of the professor's second rule, you get your candy bar!
Of course the rules actually guarantee a candy bar to \emph{every}
student, no matter how far back in line they may be.

\endinput