Problem Solving & Reasoning

Develop conjectures, test them, and explain solutions using patterns, deduction, and Polya’s model.

Learning goals

  • Distinguish induction from deduction.
  • Use counterexamples and algebraic proofs.
  • Choose a strategy, check a result, and extend a problem.

Induction and conjectures

When a pattern appears in several examples, we naturally wonder whether it continues. That observation can suggest a conjecture, but it does not settle the claim. We will distinguish discovering a plausible rule from proving that it works in every required case.

Inductive reasoning starts with specific cases and proposes a general conclusion, called a conjecture. A conjecture still needs proof. A finite list alone does not determine a unique continuation.

A doubling pattern

What is the \(n\)th term in the sequence \(1,2,4,8,\ldots\)? State the pattern you are using.
Show worked solution

Each displayed term is twice the preceding term. Starting with the first term at n=1 gives:

\[a_n=2^{n-1}\]

Check: n=1,2,3,4 gives 1,2,4,8. This is the formula under the doubling rule; the finite list alone does not prove that this is the only possible rule.

A triangular arrangement

How many circles are in a two-dimensional pyramid with \(n\) rows? The top row contains one circle, the next two circles, and each succeeding row one more circle, so the bottom row contains \(n\). Explain your answer.
Show worked solution
\[T_n=1+2+\cdots+n\]

Write the same sum in reverse and add the two lists term by term. There are n pairs, each totaling n+1.

\[2T_n=n(n+1)\quad\Longrightarrow\quad T_n=\frac{n(n+1)}2\]

For four rows, 1+2+3+4=10, agreeing with the formula.

Patterns and counterexamples

What one counterexample can establish

A counterexample is an allowed case in which a proposed universal claim fails.

It disproves that claim even when many earlier examples worked. It does not automatically tell us the correct replacement rule, so separate rejecting a conjecture from constructing a new one.

An apparent pattern is a place to begin asking questions. Test it against an unusual case, a boundary case, or the next example that looks different. One counterexample can overturn a universal claim, while many confirming examples still leave a proof to do. We will use this distinction to decide when a conjecture needs revision.

Look-and-say sequence

Find the next four terms of \(1,11,21,1211,111221,312211,\ldots\). Explain the rule.
Show worked solution

Read each run of identical digits in the previous term. For example, 21 is “one 2, one 1,” giving 1211.

Previous termRead its runsNext term
312211one 3, one 1, two 2s, two 1s13112221
13112221one 1, one 3, two 1s, three 2s, one 11113213211
1113213211three 1s, one 3, one 2, one 1, one 3, one 2, two 1s31131211131221
31131211131221one 3, two 1s, one 3, one 1, one 2, three 1s, one 3, one 1, two 2s, one 113211311123113112211

A repeating decimal

What is the \(2026\)th decimal digit of \(\frac17\)? Count the first digit after the decimal point as position one.
Show worked solution
\[\frac17=0.\overline{142857},\qquad2026=6\cdot337+4\]

The six-digit block repeats. After 337 complete blocks, the required digit is the fourth digit of 142857, which is 8.

A universal claim

Is the square of every real number always positive? If false, give a counterexample.
Show worked solution
\[0^2=0\]

Zero is neither positive nor negative. The claim is false. The correct statement is that every real square is nonnegative.

Test four statements

For each statement, determine whether it is true for every real number \(x\). If it is false, provide a counterexample.
  • \(\sqrt{x^2}=x\)
  • \(|x|>0\)
  • \(x+x\ge x\)
  • \(|x+3|=|x|+3\)
Show worked solution
StatementCounterexampleConclusion
\(\sqrt{x^2}=x\)\(x=-1:\ \sqrt{(-1)^2}=1\ne-1\)False; the square root equals |x|.
\(|x|>0\)\(x=0:\ |0|=0\)False; absolute value is nonnegative.
\(x+x\ge x\)\(x=-1:\ -2<-1\)False; it holds precisely when x≥0.
\(|x+3|=|x|+3\)\(x=-3:\ 0\ne6\)False; absolute value does not distribute over addition.

Deduction and proof

A pattern gives us a promising conjecture, but further examples cannot by themselves prove it. We now need a reason that covers every permitted case. Keep asking which assumptions each step uses and whether a counterexample could still escape the argument.

Deductive reasoning reaches a conclusion by applying general assumptions, established properties, formulas, or theorems.

Area of a circle

Find the area of a circle with radius 5 units.
Show worked solution

Use the area formula with r=5.

\[A=\pi r^2=\pi(5)^2=25\pi\text{ square units}\]

This is exact; approximately 78.54 square units.

A right triangle

The two legs of a right triangle measure 15 and 8 units. Find the length of the hypotenuse.
Show worked solution
\[c^2=15^2+8^2=225+64=289\]\[c=\sqrt{289}=17\text{ units}\]

Use the positive root because a length is positive.

An even-number proof

Prove that the sum of two even integers is even.
Show worked solution

Let the two even integers be 2m and 2n, where m and n are integers.

\[2m+2n=2(m+n)\]

Since m+n is an integer, the sum is a multiple of two, so it is even.

Conjecture and prove a number trick

Pick a number. Multiply it by 8, add 6, divide the sum by 2, and subtract 3. Form a conjecture about the result and prove it.
Show worked solution

Try 2: the steps give 16,22,11,8. Try 5: they give 40,46,23,20. Conjecture: the result is four times the original number.

\[\frac{8x+6}{2}-3=4x+3-3=4x\]

This algebra proves the conjecture for every real starting number x.

Mathematical induction is a proof, not a pattern guess

To prove a statement P(n) for every integer n≥1 by mathematical induction, establish P(1), then show that for an arbitrary k≥1, P(k) implies P(k+1). The base starts the chain and the implication advances it. Checking many separate cases is inductive reasoning, but it does not supply this implication.

Prove a sum formula

Prove \(1+3+\cdots+(2n-1)=n^2\) for every integer \(n\ge1\).

Show worked solution

Base: for \(n=1\), both sides equal one. Assume the sum through \(2k-1\) equals \(k^2\). The next odd number is \(2(k+1)-1=2k+1\), so the sum through it is \(k^2+2k+1=(k+1)^2\). This proves the implication for arbitrary k and completes induction. We assumed only the k case temporarily; we did not assume the desired k+1 conclusion.

Polya’s four steps

A difficult problem becomes more manageable when we separate understanding, planning, carrying out the plan, and checking. You may need to move back and forth between these stages. Revising an unsuccessful plan is part of solving the problem, not evidence that you should stop.

  • Understand the problem: identify the data, unknowns, and constraints.
  • Devise a plan: choose a representation or strategy.
  • Carry out the plan: show the reasoning and calculations.
  • Look back: check the result and consider extensions.
A solution explains why the method works. An answer alone does not show the reasoning.

Grid routes

Let us turn the general planning advice into a counting strategy. Instead of listing complete routes immediately, ask how a route can arrive at one chosen point. Combining the possibilities from its allowed predecessors makes a large count manageable, but only if we keep the permitted directions and boundary conditions consistent.

Allison’s walk

Allison wishes to walk along the streets from point A to point B in the map below. How many direct routes can she take? A direct route uses only movements toward B: four blocks right and three blocks down, with no backtracking.
Show worked solution

Understand: the street map is a 4-by-3 grid. Every direct route has seven steps: four right (R) and three down (D). Plan: choose which three positions contain D.

\[\binom73=\frac{7!}{3!4!}=35\]

There are 35 direct routes. Check by adding incoming route counts at each junction: the bottom row becomes 1,4,10,20,35.

Passing the café

Using the same map, how many direct routes from A to B pass Starbucks on Third Avenue? How many avoid it? Treat passing the café as walking along the marked street segment between Board Walk and Park Avenue.
Show worked solution

There are 3 routes from A to the left end of that segment: one right and two down. After walking right along the segment, 3 routes remain to B: two right and one down.

\[\text{Pass the café: }\binom31\binom31=3\cdot3=9\]\[\text{Avoid the café: }35-9=26\]

The café lies along an edge of the grid, not at an intersection; require that edge in the count.

Change the grid size

Suppose the simplified street map is a 4-by-5 grid. How many direct routes connect its upper-left and lower-right corners?
Show worked solution
\[\binom94=\frac{9\cdot8\cdot7\cdot6}{4\cdot3\cdot2\cdot1}=126\]

A route contains four steps in one direction and five in the other.

Reverse the question

A street map is a \(3\times m\) grid. Allison finds 35 direct routes from its upper-left to lower-right corner. What is \(m\)?
Show worked solution
\[\binom{m+3}{3}=35\]

For positive integer m, test the increasing counts: m=1 gives 4, m=2 gives 10, m=3 gives 20, and m=4 gives 35. Thus m=4; later counts are larger.

In general, an \(m\times n\) grid has \(\binom{m+n}{m}\) shortest routes. Choose the positions of one direction’s steps. Explore the counts below.

Working backwards

In the route-counting problem we organized the possibilities from a starting point. Another strategy is to begin with the required final state and undo the steps. Ask which operation would reverse the last change, then continue in reverse order. Once you reach a proposed starting value, run the original process forward to check it.

John’s three days at the fair

John played a game of chance for three consecutive days. On the first day, he doubled his money and spent ₱300. On the second day, he tripled his money and spent ₱540. On the third day, he quadrupled his money and spent ₱720. He had ₱480 when he left the fair on the third day. How much money did John start with?
Show worked solution

Undo the last subtraction before undoing the last multiplication. Work backward one day at a time.

\[\text{Before day 3: }(480+720)/4=300\]\[\text{Before day 2: }(300+540)/3=280\]\[\text{Initially: }(280+300)/2=290\]

John started with ₱290. Check forward:

\[290\cdot2-300=280,\quad280\cdot3-540=300,\quad300\cdot4-720=480\]

Simplifying a difficult sum

What makes a sum telescope

A telescoping sum is arranged so that most terms cancel between neighboring parts, leaving a small number of boundary terms.

Write out the first few and last few terms to see what survives. Cancellation is justified by the actual terms, not merely by a pattern suggested by the notation.

A long calculation may be an invitation to look for structure. Compare neighboring terms or pair terms before reaching for repeated arithmetic. The useful pattern is the one that explains the entire sum, including its first and last terms; these endpoints are often where an otherwise promising argument needs correction.

A telescoping sum

Find the value of \(\frac12+\frac16+\frac1{12}+\frac1{20}+\cdots+\frac1{999000}\). The denominators are products of consecutive positive integers.
Show worked solution
\[\frac1{k(k+1)}=\frac1k-\frac1{k+1}\]

The last denominator is 999×1000. Rewrite every term so that adjacent terms cancel.

\[\left(1-\frac12\right)+\left(\frac12-\frac13\right)+\cdots+\left(\frac1{999}-\frac1{1000}\right)\]\[=1-\frac1{1000}=\frac{999}{1000}\]

An infinite radical

Simplify \(\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}\), interpreted as the limit of its finite truncations.
Show worked solution

Set a₁=√2 and aₙ₊₁=√(2+aₙ). The first term is less than 2. If aₙ<2, then aₙ₊₁<√4=2, so the sequence stays bounded above by 2. It is increasing: the first step increases and the square-root map preserves inequalities. Thus a limit L exists.

\[L=\sqrt{2+L}\quad\Longrightarrow\quad L^2-L-2=(L-2)(L+1)=0\]

Because the limit is nonnegative, reject −1. The value is 2.

Investigation and checking assumptions

Before accepting an answer, return to the wording of the problem. Did we count the intended objects, use all the conditions, and exclude impossible cases? A clear explanation of those checks can be as important as the calculation itself.

Regions in a circle

Mark n distinct points on a circle and join every pair by chords. Arrange the points so that no three chords meet at one interior point. Investigate the number of regions. Does the initial pattern continue by doubling?
Show worked solution

For n=1,2,3,4,5 the maximum counts are 1,2,4,8,16. Each new chord adds one more region than its number of interior crossings. There are C(n,2) chords. Every choice of four points determines exactly one interior crossing, so there are C(n,4) crossings.

\[R_n=1+\binom n2+\binom n4\]\[R_6=1+15+15=31\]

The next value is 31, not 32. The first five cases suggest doubling but do not prove it. The no-three-concurrent condition ensures crossings are counted separately.

The census taker

A census taker asks a woman how many children she has and their ages. She replies: “I have three children. The product of their ages is 36, and the sum of their ages is the house number next door.” The census taker checks that number, returns, and says, “I need more information.” The woman replies, “I have to go; my oldest child is sleeping upstairs.” The census taker now knows their ages. How old are the three children? Assume positive whole-number ages.
Show worked solution

List every unordered positive-integer triple with product 36 and calculate its sum.

AgesSum
1, 1, 3638
1, 2, 1821
1, 3, 1216
1, 4, 914
1, 6, 613
2, 2, 913
2, 3, 611
3, 3, 410

The census taker knows the sum but still cannot decide. Only 13 occurs twice, leaving (1,6,6) and (2,2,9). The statement “my oldest child” supplies a unique oldest child. This eliminates the two six-year-olds, so the ages are 2,2,9. Merely giving the product and saying “there is a unique oldest” would not supply all these clues.

A guarantee needs both a bound and an example

The pigeonhole principle says that placing more than r objects into r boxes forces some box to contain at least two objects. More generally, if every box had at most k objects, the total could not exceed rk. Therefore rk+1 objects force at least k+1 in one box. To prove this number is the smallest guarantee, also show how rk objects can avoid the desired outcome.

Enough cards to force a repeated label

Cards have one of five labels, with unlimited cards of each label. What is the smallest number drawn that guarantees four cards with the same label, regardless of order?

Show worked solution

With \(15\) cards, three of each label avoid four matching cards. With \(16\), assuming at most three of each would allow at most \(5\cdot3=15\), a contradiction. Thus \(16\) is both sufficient and minimal. A likely outcome and a guaranteed outcome are different claims.

Practice and extensions

A growing circle pattern

If the diagrams below continue, how many circles will the \(n\)th diagram contain? Explain. Each diagram is a U-shape with \(n\) circles in each upright column and \(n+1\) circles across the bottom, including the two corners.
Show worked solution

Count both upright columns, then the bottom circles strictly between them. The corners must not be counted twice.

\[2n+(n-1)=3n-1\]

The first four counts are 2,5,8,11, matching the diagrams.

Caryl and Darius see the same figure

For the U-shaped circle pattern above, Caryl gives \(2n+(n-1)\) and Darius gives \(n(n+1)-(n-1)^2\). Explain how each may be seeing the figure and show that the answers agree.
Show worked solution

Caryl counts two columns of n circles and the n−1 bottom interior circles. Darius starts with a full n-by-(n+1) rectangle of circles, then removes the (n−1)-by-(n−1) interior block above the bottom row.

\[2n+(n-1)=3n-1\]\[n(n+1)-(n-1)^2=n^2+n-(n^2-2n+1)=3n-1\]

Both decompositions count the same circles.

Two piles of cards

A standard deck of 52 playing cards, containing 26 red and 26 black cards, is cut into two groups of 26 cards each. Find the ratio of the number of red cards in one group to the number of black cards in the other group.
Show worked solution

Let r be the number of red cards in the first group. Because it contains 26 cards, its black count is 26−r. The total black count is 26, so the second group contains 26−(26−r)=r black cards.

\[\text{Red in group 1}=\text{black in group 2}=r\]

If r>0, the ratio is 1:1. If r=0, both counts are zero and the ratio is undefined; the equality of the counts always holds. Random cutting does not change the argument.

Diagrams and elimination

Some problems hide their structure in a paragraph of conditions. A diagram or organized list can make those conditions visible and help rule out impossible cases. We will choose a representation that preserves the information, then check the surviving possibility against every condition.

A walk on Earth

You are standing on the surface of the Earth. You walk one mile south, one mile west, and one mile north, ending exactly where you started. Where are you? Treat Earth as a sphere and directions as geographic directions.
Show worked solution

One answer is the North Pole. Walking south reaches a parallel one mile from the pole. Walking west changes longitude; walking north one mile then returns to the North Pole.

There are also infinitely many starting points near the South Pole. Choose a parallel whose circumference is 1/k mile, for a positive integer k. Start one mile north of that parallel. The southward leg reaches it; walking one mile west makes exactly k complete circuits; the northward leg retraces the first leg to the start. Thus the North Pole is not the only solution.

Who plays which instrument?

Carol, Sue, Dave, and Jim each play a different instrument in the school band. The available instruments are clarinet, flute, saxophone, trombone, and harmonica. Determine who plays which instrument from these clues:
  • Carol plays either the clarinet, saxophone, or harmonica.
  • Sue does not play the flute.
  • Dave does not play the trombone, saxophone, flute, or clarinet.
  • Jim plays either the harmonica or the saxophone.

There are five listed instruments and four students, so one instrument is unused.

Show worked solution
  • Dave must play the harmonica: all four other choices are excluded.
  • Jim cannot use Dave’s instrument, so he plays the saxophone.
  • Carol cannot use either of those instruments, leaving the clarinet.
  • Sue can choose only flute or trombone; the clue excludes flute, leaving trombone.
StudentInstrument
CarolClarinet
SueTrombone
DaveHarmonica
JimSaxophone

The flute is unused. Check that every clue holds and no instrument is assigned twice.

Additional practice: mixed exercises

Check a proposed rule

These follow up the slide investigations. Give a reason rather than relying on a few examples.

  1. The circle-region counts begin \(1,2,4,8,16\). A student predicts \(32\) regions for six points. Evaluate this prediction when no three chords meet inside the circle.
  2. A student says that the red-card/black-card ratio in the two equal deck halves must always be \(1:1\). What happens if one half contains all black cards?
Show worked solution
  1. Count chords and crossings: \(1+\binom62+\binom64=1+15+15=31\). The initial doubling pattern is not a proof.
  2. The compared counts are both zero. Their equality still holds, but \(0/0\) is undefined. State the \(1:1\) ratio only when the common count is positive.

Test a claim and apply a theorem

For each universal claim, use real numbers. A single counterexample disproves a universal claim.

  1. Is \(\sqrt{x^2}=x\) true for every real \(x\)?
  2. Is \(|x|>0\) true for every real \(x\)?
  3. Is \(x+x\ge x\) true for every real \(x\)?
  4. Is \(|x+3|=|x|+3\) true for every real \(x\)?
  5. Find the area of a circle of radius \(5\) units.
  6. A right triangle has legs of lengths \(15\) and \(8\) units. Find the hypotenuse.
Show worked solution
  1. No. For \(x=-1\), \(\sqrt{x^2}=1\ne-1\). The correct identity for all real \(x\) is \(\sqrt{x^2}=|x|\).
  2. No. At \(x=0\), \(|x|=0\). The universally true statement is \(|x|\ge0\).
  3. No. At \(x=-1\), the claim would be \(-2\ge-1\), which is false. Subtracting \(x\) from both sides shows the original inequality holds exactly when \(x\ge0\).
  4. No. At \(x=-3\), the left side is \(0\) and the right side is \(6\). Absolute value does not generally distribute over addition.
  5. Apply \(A=\pi r^2\). Substituting the given radius gives \(A=\pi\cdot5^2=25\pi\) square units.
  6. By the Pythagorean theorem, \(c^2=15^2+8^2=225+64=289\). Length is positive, so \(c=\sqrt{289}=17\) units.

Takeaways and connections

  • Patterns suggest; proofs justify.
  • A counterexample defeats a universal claim.
  • Keep every clue and constraint visible before choosing a strategy.
  • Check exceptional cases and consider extensions.

Review logical reasoning →

Reasoning, connections and deeper practice

Looking back can mean asking whether the method works for an entire family, not just checking one numerical answer. Here an invariant rules out a process, while a construction shows why finitely many observations cannot prove a pattern.

Reasoning · An invariant rules out a target

Start with \(0\). Each move adds \(6\) or subtracts \(4\). Can the process ever reach \(15\)? Can it reach \(14\)? Justify both answers without listing every possible sequence.

Hint

Track parity, then construct a route for the target that is not ruled out.

Show worked solution

Every move changes the value by an even integer, so all reachable numbers are even. Thus \(15\) is impossible. Parity alone does not prove every even target is reachable, but \(14\) has an explicit construction: \(0\to6\to12\to18\to14\). A necessary condition can rule something out; a construction proves a particular target possible.

Advanced / Honors · Two rules fit the same observations

The first four terms are \(1,2,4,8\), indexed from \(n=1\). Construct two formulas agreeing with all four terms but giving different fifth terms. Explain what additional statement would justify the usual answer \(16\).

Hint

Add to the doubling formula a product that vanishes at the first four indices.

Show worked solution

Take \(a_n=2^{n-1}\) and \(b_n=2^{n-1}+(n-1)(n-2)(n-3)(n-4)\). At each of \(n=1,2,3,4\), one factor in the added product is zero. At \(n=5\), however, \(a_5=16\) and \(b_5=40\). An explicit recurrence such as \(a_1=1\), \(a_{n+1}=2a_n\) would determine the continuation. The finite observations alone do not establish that recurrence.

HM Math Studio

Opening your learning space…