University Discrete Mathematics — Induction and Recursion Worksheet

All 10 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1Mathematical Induction for Summation Formulas

   The notation ${\displaystyle {\sum }_{i=1}^n(4i-1)}$ means the sum of $4i-1$ over $i=1,2,\dots ,n$, that is $3+7+11+\dots +(4n-1)$. Let $P(n)$ be the statement $${\sum }_{i=1}^n(4i-1)=n(2n+1),n\in {\mathbb{Z}}^{+}.$$

   1. Write out the sum for $n=4$ term by term and check that $P(4)$ is true.
   2. Write the statements $P(k)$ and $P(k+1)$.
   3. Assuming $P(k)$, show that $P(k+1)$ follows. Say at which step you use $P(k)$.
   4. Which value of $n$ must the base case check, and why?
2. Q2Mathematical Induction for Summation Formulas

   Prove by induction that for every $n\in \mathbb{N}=\{0,1,2,\dots \}$, $${\sum }_{i=0}^{n}2·3^i=3^{n+1}-1.$$

3. Q3Induction for Divisibility and Inequalities

   Prove by induction that $4\mid 5^n+3$ for every $n\in \mathbb{N}=\{0,1,2,\dots \}$.

4. Q4Induction for Divisibility and Inequalities

   Prove by induction that $3^n\ge 2n+1$ for every $n\in \mathbb{N}=\{0,1,2,\dots \}$. State clearly where your inductive step uses an inequality that needs $k\ge 0$.

5. Q5Strong Induction

   A café sells muffins only in boxes of $3$ and boxes of $7$. An order of $n$ muffins can be filled exactly when $n=3a+7b$ for some $a,b\in \mathbb{N}=\{0,1,2,\dots \}$.

   1. Show that orders of $12$, $13$ and $14$ muffins can be filled, and that an order of $11$ cannot.
   2. Use strong induction to prove that every order of $n\ge 12$ muffins can be filled.
   3. Why does your proof need three base cases rather than one?
6. Q6Strong Induction

   A sequence is defined by $d_1=1$, $d_2=2$, $d_3=3$ and $d_n=d_{n-1}+d_{n-3}$ for $n\ge 4$.

   1. Compute $d_4$ through $d_8$.
   2. Use strong induction to prove that $d_n\le 2^{n-1}$ for every $n\in {\mathbb{Z}}^{+}$.
7. Q7Recursively Defined Sequences
   1. Let $a_0=3$ and $a_n=2a_{n-1}-1$ for $n\ge 1$. Compute $a_1$ through $a_5$.
   2. Let $b_1=1$, $b_2=4$ and $b_n=b_{n-1}+n{b}_{n-2}$ for $n\ge 3$. Compute $b_3$, $b_4$ and $b_5$.
   3. Give a recursive definition (initial term and rule) of the sequence $5,8,11,14,\dots$ and of the sequence $2,6,18,54,\dots$, starting each at index $1$.
   4. For $n\in {\mathbb{Z}}^{+}$ let $s_n={\displaystyle {\sum }_{i=1}^n{i}^2}$. Give a recursive definition of $s_n$ that uses no $\sum$ sign.
8. Q8Recursively Defined Sequences

   A sequence is defined by $u_0=3$ and $u_n=u_{n-1}^2-2u_{n-1}+2$ for $n\ge 1$.

   1. Compute $u_1$, $u_2$ and $u_3$.
   2. Prove by induction that $u_n=2^{2^n}+1$ for every $n\in \mathbb{N}=\{0,1,2,\dots \}$.
9. Q9Recursive Algorithms and Their Correctness

   The procedure $\mathrm{C}\mathrm{U}\mathrm{B}\mathrm{E}$ takes $n\in \mathbb{N}=\{0,1,2,\dots \}$ and is defined by: if $n=0$, return $0$; otherwise return $\mathrm{C}\mathrm{U}\mathrm{B}\mathrm{E}(n-1)+3n(n-1)+1$.

   1. Trace $\mathrm{C}\mathrm{U}\mathrm{B}\mathrm{E}(3)$: list the calls it makes and the value each one returns.
   2. Explain why $\mathrm{C}\mathrm{U}\mathrm{B}\mathrm{E}(n)$ terminates for every $n\in \mathbb{N}$.
   3. Prove by induction that $\mathrm{C}\mathrm{U}\mathrm{B}\mathrm{E}(n)$ returns $n^3$ for every $n\in \mathbb{N}$.
10. Q10Synthesis — drawing on several topics in this unit

    A sequence is defined by $w_0=2$ and $w_n=w_{n-1}^2-w_{n-1}+1$ for $n\ge 1$.

    1. Compute $w_1$ through $w_4$.
    2. Prove by induction that $w_n$ leaves remainder $3$ on division by $4$ for every $n\in {\mathbb{Z}}^{+}$.
    3. Why must the base case be $n=1$ and not $n=0$?

The 7 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

Sigma notation, and what a summation formula claims

Σ is an instruction to add. The letter under it is the index, the numbers below and above are where the index starts and stops, and the expression after it is the term. Q1 spells the notation out and then asks you to use it: write the sum for one small value of n term by term, add the terms, and compare with what the formula predicts for that n. That comparison is exactly what "check the statement" means, and it is also the base case of the proof.

The template every induction proof follows

The principle is the same in all ten questions on this set. If the statement holds at the starting value, and if its holding at one stage forces it to hold at the next, then it holds at every stage from the start onwards.

Q2 runs the same template with no scaffolding and with a different starting value: the range is stated with the statement, and the first value in that range is the one the base case has to check. The terms are powers, so the laws of exponents do the work of the step; factor rather than expand, and keep the target for k + 1 written at the bottom of the page so you can see when you have arrived at it.

Induction for divisibility

Q3 proves a divisibility statement, so the first job is to say what divisibility means in a form algebra can use. a | b says that b is a times an integer — so the hypothesis gives you an integer, and the step must end by exhibiting another one.

Induction for an inequality

Q4 replaces the equals sign with ≥, and that changes the shape of the step. An equality proof is a chain of equalities; an inequality proof is a chain in which each link may weaken the statement, provided it weakens it in the right direction.

Work from the left side of P(k + 1) towards the right, applying the hypothesis to replace a piece by something you know is no larger, and keeping the direction of every sign the same. If you need to run the chain the other way, say so in words rather than reversing signs silently.

Strong induction, and how many base cases to check

Ordinary induction assumes the statement at k and proves it at k + 1. Strong induction assumes it at every value from the start up to k, and that is what a question needs when the step reaches back further than one stage — or back by an amount you cannot pin down in advance.

Q5 is the standard setting: quantities built from two fixed sizes, where filling an order of n is reduced to filling a smaller order and adding one more box. Part (a) is a hands-on check of a few small orders, including one that cannot be filled — a counterexample is exhibited, not argued. Part (b) turns the reduction into a proof, and part (c) asks why more than one base case is needed.

Q6 makes the same point with a sequence whose rule looks back three terms. Part (a) is arithmetic: run the rule forwards and tabulate. Part (b) proves a bound on every term, and the step needs the bound at more than one earlier index, so ordinary induction has nothing to offer. Write which earlier cases the step uses before you write the step itself.

Sequences defined by recursion

A recursive definition has two halves: one or more initial terms, and a rule that gives aₙ in terms of earlier terms, valid from a stated index onwards. Neither half is optional — without the initial terms the rule computes nothing.

Q7 works in both directions. Parts (a) and (b) read a definition forwards: substitute, compute, and keep a column of values — in (b) the rule uses the two previous terms and the index n itself, so the multiplier changes at every stage, which is the whole reason to write the substitution out rather than doing it in your head. Part (c) runs backwards, from a listed pattern to a definition: decide first whether consecutive terms differ by a fixed amount or by a fixed factor, then write the initial term and the rule, with the index the question asks you to start at. Part (d) is the same move applied to a sum: a partial sum of n terms is the partial sum of n − 1 terms plus the nth term, and that one sentence is the whole recursion.

Q8 joins the two ideas of the set: a sequence given recursively, and a closed formula for its nth term to be proved by induction. Part (a) is computation. In part (b) the hypothesis is the formula at k, the recursion is what lets you write the term at k + 1 in terms of it, and the exponent laws — a power of a power, an exponent that is itself a power of two — are what turn the result into the formula at k + 1. Write the target for k + 1 down first; the algebra is then aimed at something instead of wandering.

Recursive algorithms and their correctness

A recursive procedure is a recursive definition written as instructions: a base case that returns a value outright, and a case that calls the procedure on a smaller input and combines the result. Q9 asks the three questions every recursive procedure has to answer.

Nothing in this set asks how long a procedure takes — counting operations and comparing growth rates belong to a later course. What is asked is that it stops, and that what it returns is what was claimed.

The synthesis question

Q10 puts the whole set into one chain. Part (a) is Q7's forward computation on a new rule. Part (b) proves a statement about every term — but the statement is about a remainder on division, so the hypothesis has to be turned into an equation the way Q3 turned divisibility into one, and then substituted into the recursion. Part (c) returns to the first decision of all: which value the base case must check, and why the range the claim is made for settles it.

Preview all 5 pages

Click any page to open the full PDF.

Getting the most out of it

Write P(k) and P(k + 1) before you start

Both, in full, at the top of the page: one is everything you are allowed to assume, the other is exactly what you have to reach. Most failed inductive steps are algebra aimed at nothing in particular, and this one habit fixes them.

Label the line where the hypothesis is used

Every proof on this set has one line that is the whole argument. Mark it. If you cannot find it, you have either written a direct proof by accident or left a gap where the hypothesis should have been.

Compute the first few terms, always

Before proving anything about a recursively defined sequence, run the rule forwards for four or five stages. It confirms you have read the rule correctly, it shows how far back the rule reaches, and it tells you how many base cases your proof is going to need.

Finish with a sentence, not an expression

"This is 4 times an integer, so the statement holds at k + 1." "Hence by induction the statement holds for every n in the stated range." Written work in this course is marked on the quality of the writing as well as the algebra, and the closing sentence is where a correct calculation turns into a proof.

Common questions