symbol	write
<	`<`
≤	`<=`
=	`=`
≠	`!=`
≥	`>=`
>	`>`

symbol	write	remark
∧	`/\`	and (also `and` works)
∨	`\/`	or (also `or` works)
¬	`!`	not (also `not` works)
F	`FF`	false
T	`TT`	true
U	`UU`	undefined
→	`-->`	material implication
↔	`<->`	material equivalence
&&	`&&`	short-circuit and
\|\|	`\|\|`	short-circuit or

symbol	write	remark
⇒	`==>`
⇐	`<==`
⇔	`<=>`	treats U and F as equivalent
≡	`===`	treats U and F as different

symbol	write
∀ x:	`AA x:`
∀ x; 0 ≤ x < y:	`AA x; 0 <= x < y:`
∃ x:	`EE x:`
∃ x; x + 2 ≠ z:	`EE x; x+2 != z:`

An Induction Problem Inspired by Alarfaj and Sangwin 2022

Instructions • The Goal • The Base Case • The Induction Step • Alarfaj's and Sangwin's Tasks • Comments

Antti Valmari 2025-04-09 (Small language fixes 2025-05-22)

This web page is based on the running example in Maryam Alarfaj & Chris Sangwin, “Updating STACK Potential Response Trees Based on Separated Concerns”, iJET ‒ Vol. 17, No. 23, 2022, DOI 10.3991/IJET.V17I23.35929. The example consists of three tasks that are related to finding an induction proof of a certain summation formula. In this web page the proof is dealt with in full and it has been organized similarly to how such proofs are typically presented in textbooks. The tasks have been formulated so that our feedback tool can check the answers, although it has no feature for representing summations. While STACK emphasises assessment, our tool has been designed for learning by trying tasks, getting feedback, and trying again with an improved answer.

Instructions

Our feedback too is called MathCheck. It does not know who you are and it does not store your answers. Feel free to try both correct and incorrect answers!

Light brown regionsCongratulations! You made this visible! contain hidden text that becomes visible when you move the mouse cursor there. Help for typing mathematical symbols is available at the top right part of the screen.

The Goal

The goal is to prove, for every natural number n, the following formula using mathematical induction:

∑

k = 1

(2k − 1)² =

n (2n − 1) (2n + 1)

The Base Case

What is the base case of the induction proof? Please fill in the boxes! Feel free to simplify or not simplify the right hand side. Hint 1The base case must state what the original formula (1) states when n = 0. Hint 2Replace every instance of n in (1) by 0.

∑

Why are the left and right hand sides equal in the base case? AnswerWhen n = 0, the right hand side of the original formula (1) obviously yields 0. Also the left hand side yields 0, because then it is a sum over an empty range.

The Induction Step

In this exercise, a linear factor is something like −3n + 4 or anything simpler.

If the right hand side has not been simplified at all, it looks horrible. Fortunately, it lends itself to a couple of simple simplifications. Do them! The result should be a product of linear factors, optionally divided by a number. Suggestions:

It may be helpful to copy the previous answer to be used as a starting point.
You may modify the answer in place. Alternatively, take a copy, write “=”, and paste the copy. The latter has the advantage that if you accidentally break the answer, the previous step remains available.
After each modification or copying, click “to new tab” or “to the right” to see whether it is correct. Red feedback with a counter-example means that there is a mathematical error. Fuchsia feedback means that the answer is otherwise correct but in a wrong form (e.g., too long).

We must show that the left hand side of (2) is equal to the simplified right hand side of (2). We will do so in the next few steps.

The light brown region “LHS” below contains the correct left hand side of the previous answer. Rewrite it in a form that makes it possible to apply the induction assumption! What does “application of the induction assumption” mean?It means using the formula to be proved as a justification of a step in the proof of the induction step. It is not circular reasoning, because of the following. The goal of the induction step is to prove that if the original claim holds for n, then it also holds for n + 1. The original claim is thus in the if-part. HintSplit the left hand side of (2) to consist of the left hand side of (1) and the rest.

LHS

n + 1

∑

k = 1

(2k − 1)²

∑

Transform the result of the previous task to a product of linear factors, optionally divided by a number! Suggestions:

Again, it may be helpful to write intermediate results separated from each other by “=”, and to click “to new tab” or “to the right” after writing each of them.
You may get the first intermediate result by copying the contents of the boxes of the previous answer and the “+” between them.
Ignore the “must be in linear factor form” messages until you are almost ready. First focus on getting rid of the outermost “+”.
This is one possible way of doing it: Hint 1Simplify 2(n + 1) − 1, if you have not done that already. Hint 2Transform the expression to everything else divided by 3. Hint 3Make 2n + 1 a common factor of the sum above the division line. Hint 4Transform the part other than (2n + 1) above the division line to a quadratic polynomial. Hint 5To factor the quadratic polynomial, find its zeroes. Or compare it to the simplified right hand side of (2), guess the factors from that, and verify the guess by multiplying the factors.

What must be done with this result to complete the induction step? AnswerOne must check that it is equal to the right hand side of (2).

Alarfaj's and Sangwin's Tasks

The first of the three tasks in [AS22] was, in essence, the same as our (2). However, while in our case “∑” and “=” were given and the task consisted of filling in four answer boxes, in their case (1) was given the name “statement P(n)”, only one answer box was given, and the task was to write statement P(n + 1) in it. Thus realizing that the answer must be an equation (and not just its one or the other side) was part of the challenge.

Earlier on, almost 60 % of students had failed that part. This motivated the authors of [AS22] to improve the potential response tree of the problem. Originally no feedback and no points had been designed for the case where the answer is not an equation. In [AS22], feedback and partial points for this case were specified. Answers close enough to the LHS of (2) were given 0.3 points, and remaining answers mathematically equivalent to the RHS (and thus also the LHS) were given 0.4 points.

The third task was “Calculate

(n + 1) ⋅ (2 ⋅ (n + 1) − 1) ⋅ (2 ⋅ (n + 1) + 1)

−

n ⋅ (2 ⋅ n − 1) ⋅ (2 ⋅ n + 1)

writing your answer in simplified form.” Again (2(n+1)-1)^2 (and only it) was given as an answer in [AS22]. We have filled in a simplification chain as an example of what solving the problem step by step could produce. It can be changed or wiped out, to try other possibilities.
there is a mild length limit
only a shortest possible goes

or

Comments

The treatment in [AS22] established the same technical facts as our induction step, but differed in how they were organized. We started with the LHS of (2) and derived its RHS, using (1) as the induction assumption. In [AS22], the LHS of (1) was subtracted from the LHS of (2), the same was done with the RHSs, and the results turned out the same. It is unclear to us why this shared answer was (2 ⋅ (n + 1) − 1)² instead of (2 ⋅ n + 1)².

The assessment and feedback mechanism of STACK relies on knowing or guessing frequently occurring incorrect answers, and designing feedback for each of them manually. The main feedback mechanism of our tool does not need such work at all. It consists of providing an automatically generated counter-example when the answer is incorrect. The teacher has the option, but no obligation, of telling the tool to do additional checks. For instance, a limit to the length of answers was used many times above, and sometimes an answer was required to be in a certain form. Employing such checks does not require knowledge or guesses of the incorrect answers that students tend to make.

On the other hand, our tool has no assessment mechanism. It has, however, sometimes been used as an answer-checking machine of another tool which keeps track of points.