Begging the Question in Proofs - Vancouver Computer Science Tutoring

A Common Mistake

When I was teaching the introductory logic course at UBC, called CPSC 121, one of the most common mistakes I saw in students’ proofs was a mistake called “begging the question”. Markers would annotate this mistake as “BtQ” in the margins of assignments and exams that were returned to students.

Begging the question is a subtle mistake. Let’s explore it in more detail in today’s blog post. After reading this post, you should be able to recognize if you are begging the question in one of your proofs, and be able to restructure a proof to correct this logical error.

Its General Form

The simplest way to describe begging the question is: you start by assuming the very thing you want to prove. Incorrect proofs that beg the question typically take this three-step “BtQ form”:

[The thing I want to prove]
$\Rightarrow$ [Some math]
$\Rightarrow$ [Something that’s obviously true]

Let’s dive straight into an example of begging the question to see this incorrect three-step BtQ form in action. After we do that, we’ll correct the error and demonstrate how to structure the proof correctly.

Begging the Question With Induction

The most common place begging the question shows up is in the inductive step of a proof by induction. Let’s consider the following proof by induction question, which appears in most introductory texts:

Prove that the sum of the first $n$ integers is equal to $n(n+1)/2$. Or, more formally, prove that
\begin{equation}
\sum_{i=1}^n{i} = \frac{n(n+1)}{2}~\forall~n \in \mathbb{Z} \ge 1 \;.
\end{equation}

The overall structure for a proof of this statement should look like the following:

$\textbf{Inductive Step}$

Prove that if the statement holds true when $n$ is equal to some constant integer $k \ge 1$, then it follows that the statement will also hold true when $n$ is equal to $k+1$.

Or, in other words, prove that if $\sum_{i=1}^k{i} = k(k+1)/2$, for some constant integer $k \ge 1$, then it follows that $\sum_{i=1}^{k+1}{i} = (k+1)((k+1)+1)/2$.

$\textbf{Base Case}$

Prove that the statement holds true when $n = 1$. Or, in other words, prove that $\sum_{i=1}^1{i} = 1(1+1)/2$.

Let’s concentrate on the inductive step, and in particular how an incorrect proof of the inductive step might look. I start by correctly making an inductive assumption. But, immediately after making that assumption, I beg the question by outright stating the very thing I want to prove as if it were a fact. I’ve annotated the step where the error occurs with “BtQ”:

$\textbf{Inductive Step}$

Assume $\sum_{i=1}^n{i} = n(n+1)/2$ when $n = k$, for some constant integer $k$. Or, in other words, assume $\sum_{i=1}^k{i} = k(k+1)/2$ for some constant integer $k$.

\begin{align*}
\sum_{i=1}^{k+1}{i} = \frac{(k+1)((k+1)+1)}{2}~~&~~\text{[BtQ]} \\
\\
\sum_{i=1}^k{i} + (k+1) = \frac{(k+1)((k+1)+1)}{2}~~&~~\text{[Some math]} \\
\\
\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)((k+1)+1)}{2}~~&~~\text{[Some math, by assumption]} \\
\\
\frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{(k+1)((k+1)+1)}{2}~~&~~\text{[Some math]} \\
\\
\frac{k^2 + 3k + 2}{2} = \frac{(k+1)(k+2)}{2}~~&~~\text{[Some math]} \\
\\
\frac{(k+1)(k+2)}{2} = \frac{(k+1)(k+2)}{2}~~&~~\text{[Obviously true]}
\end{align*}

Note the three-step BtQ form the work takes, starting on the line annotated “BtQ”: I state the conclusion I’m trying to prove as a matter of fact, I do some math, and I reach a statement of something that’s obviously true.

Why Is It a Problem?

The incorrect proof follows the three-step form of begging the question. But, why, in general, are proofs that follow this BtQ form incorrect?

The reason it is incorrect is that the truth of the last line in the proof (denoted “Obviously true”) says nothing about the truth of the second line of the proof (denoted “BtQ”). I can start with a correct line in a proof and arrive at a correct last line, but I can just as easily (if not more easily) start with an incorrect line in a proof and arrive at a correct last line. Consider:

\begin{align*}
-1 = 1~~&~~\text{[Incorrect]} \\
\\
(-1)^2 = (1)^2~~&~~\text{[Some math]} \\
\\
1 = 1~~&~~\text{[Obviously true]}
\end{align*}
But, the fact that $1 = 1$ doesn’t mean that $-1 = 1$.

Restructuring to Create a Correct Proof

Let’s restructure the proof of the inductive step above to be correct. The tip I give my students for writing the proof of the inductive step is to do three things:

State your inductive assumption, which we’ll treat as a statement of fact to build on.
State what you need to show, assuming your inductive assumption is true, by writing “I need to show…”. Write this to remind yourself not to assume your intended conclusion is true. While I personally wouldn’t require students to write this statement on an assignment or exam, many students find it helpful to do so.
Then, start your proof from one side of the equation representing your intended conclusion, and work step by step from there to reach the other side of the equation.

Let’s work through the proof using that structure, watching how we never use the thing we want to show as if it were a statement of fact. Instead, we build towards it and reach it as the conclusion.

$\textbf{Inductive Step}$

Assume $\sum_{i=1}^k{i} = k(k+1)/2$ for some constant integer $k \ge 1$.

I $\textit{need to show}$ that $\sum_{i=1}^{k+1}{i} = (k+1)((k+1)+1)/2$.

Now, we build from one side of the equation to reach our conclusion:

\begin{align*}
\sum_{i=1}^{k+1}{i} &= \left( \sum_{i=1}^{k}{i} \right) + (k+1)~~&~~\text{[by expanding the summation]} \\
\\
&= \frac{k(k+1)}{2} + (k+1)~~&~~\text{[by our assumption]} \\
\\
&= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} & \\
\\
&= \frac{k^2+k}{2} + \frac{2k + 2}{2} & \\
\\
&= \frac{k^2 + 3k + 2}{2} & \\
\\
& = \frac{(k+1)(k+2)}{2} & \\
\\
&= \frac{(k+1)((k+1)+1)}{2}
\end{align*}

Note, at the end of all these equalities (where each line is equal to every other line), we’ve shown the following: if we rely on an assumption that, for some constant value $k$, $\sum_{i=1}^k{i} = k(k+1)/2$, then it follows that $\sum_{i=1}^{k+1}{i} = (k+1)((k+1)+1)/2$

Bringing It All Together

Now that we’ve seen how to avoid begging the question, let’s view all the pieces of the puzzle put together into a complete inductive proof.

Question: Prove $\sum_{i=1}^n{i} = n(n+1)/2~\forall~n \in \mathbb{Z} \ge 1.$
Answer:

$\textbf{Inductive Step}$

Assume $\sum_{i=1}^k{i} = k(k+1)/2$ for some constant $k \in \mathbb{Z} \ge 1$.

I $\textit{need to show}$ that $\sum_{i=1}^{k+1}{i} = (k+1)((k+1)+1)/2$.

$\textbf{Base Case}$

I $\textit{need to show}$, without relying on any assumptions, that $\sum_{i=1}^1{i} = 1(1+1)/2$.

\begin{align*}
\sum_{i=1}^1{i} &= 1 \\
\\
&= 1(1+1)/2
\end{align*}

Summary

Watch out for the three-step “BtQ form” in your inductive proofs; specifically, be careful never to assume the very thing you want to prove.

In your correct proof, be sure to clearly state what your assumption is, and differentiate that from what you need to show is true. And, while you don’t have to write down the statement, “I need to show that…”, many students find it helpful as a reminder not to beg the question.

For more tips, and to arrange for personalized tutoring for yourself or your study group, check out Vancouver Computer Science Tutoring.