26 votes
Accepted

Does a proof by induction have to explicitly refer to the principle of mathematical induction?

The appropriate level of granularity for a proof depends on the audience. If you're taking an "Intro to Proofs" class and your homework is to do some proofs by induction, then yeah, you ...
Justin Skycak's user avatar
19 votes

Why do students only see the last term of a sum abbreviated with an ellipsis?

I suspect that the issue is not so much the ellipsis per se but a problem with notation in general, and in particular with the correct use of the equals sign. At the risk of repeating what I wrote in ...
mweiss's user avatar
  • 17.3k
15 votes
Accepted

Proofs that make theorems less clear

"A well-chosen example illustrates ... and is entirely convincing." For me, all of what is usually called "generic proof" satisfy your criterion. Consider the Euclidean algorithm for finding the ...
Amir Asghari's user avatar
  • 4,428
14 votes

Good, simple examples of induction?

Here is another one: $\color{blue}{\text{Prove that the power of $13$ can be writen as a sum of two squares}}. $ I will give two proofs of it. First one is more involved and includes the following ...
nonuser's user avatar
  • 400
13 votes

Why do students only see the last term of a sum abbreviated with an ellipsis?

Encourage your students to actually read the problem to themselves, similar to how they would if they were reading a book. Starting from left to right, read the problem: "Zero squared plus one ...
celeriko's user avatar
  • 5,060
13 votes

Does induction really avoid proving an infinite number of claims?

The "avoidance of proving an infinite number of claims" explanation for the need for induction has not yet resonated with me because there are obviously many universally quantified ...
Steve's user avatar
  • 1,404
11 votes

Does induction really avoid proving an infinite number of claims?

My personal take on this, is that all the talk about "infinite this, and infinite that" is only mudding the waters. The emphasis should not be on wanting to prove $P(n)$ for all all $n$, but ...
Martin Argerami's user avatar
10 votes

Why are induction proofs so challenging for students?

As already touched on here, perhaps proof by induction should not be the first real method of proof that students learn. (The two-column proofs of geometry common in North American schools don't ...
Dan Christensen's user avatar
9 votes

'Low-algebra' examples of induction

Tiling problems might meet your constraints. A nice simple example is Golomb's Theorem that a chessboard of side $2^n$ with any square omitted can be tiled by trominoes ("L" shapes of 3 squares). In ...
Bill Dubuque's user avatar
  • 1,038
9 votes
Accepted

Is induction or recursion easier to understand?

One thing that you have to keep in mind here, is that you don't need to understand recursion to implement it. There is a big difference between "we were taught to do it like that, I implement it and ...
Dirk's user avatar
  • 1,308
9 votes

Proofs that make theorems less clear

There are many situations in which we have a clear collective understanding of intention, or goals, and examples which persuade us that these goals are plausible, as well as illustrating apparent ...
paul garrett's user avatar
  • 14.3k
9 votes

Why are induction proofs so challenging for students?

Because for us students it seems that there is no structure for it. We get the impression that there is a lot of assumption that one might do in order to prove by induction and there is no formula for ...
Douglas Silva's user avatar
9 votes

Why are induction proofs so challenging for students?

I will add my own rough theory here. Since American students are not trained in basic logic, I think the critical fact is that they have no familiarity or understanding about implication statements $P ...
Daniel R. Collins's user avatar
9 votes

Does induction really avoid proving an infinite number of claims?

The statement Since we can't go over "manually proving" all claims 1,2,… and actually get to the finish line in a finite time, we use induction to prove "all the claims at once". ...
Andrey Tyukin's user avatar
7 votes

Why are induction proofs so challenging for students?

In my experience, the most difficult part of mathematical induction is understanding where to focus my attention when creating proofs. In the two courses I've taken that teach mathematical induction, ...
Alan T's user avatar
  • 71
7 votes

Teaching strong induction instead of induction

The main problem with teaching strong induction as you define it is its logical complexity. What you seem to be doing is replacing quantification over a single integer by quantification over a set of ...
Mikhail Katz's user avatar
  • 2,142
7 votes

Good, simple examples of induction?

A simple consequnce of: Postage Stamp Problem, which states that for any two relatively prime positive integers $m,n$, the greatest integer that cannot be written in the form $am + bn$ for ...
nonuser's user avatar
  • 400
7 votes

Why do students only see the last term of a sum abbreviated with an ellipsis?

Perhaps they are misinterpreting the ellipses in $$ 0^2+1^2+2^2+\color{red}{\cdots}+n^2 = \frac{n(n+1)(2n+1)}{6}.$$ as meaning \begin{eqnarray} 0^2 & = & \frac{n(n+1)(2n+1)}{6} = \frac{0(1)(1)}...
Joseph O'Rourke's user avatar
6 votes

'Low-algebra' examples of induction

How about: A tree with $n\ge 1$ vertices has $n-1$ edges.
Aeryk's user avatar
  • 8,025
6 votes

Good, simple examples of induction?

Putnam 1963 Let $\mathbb N$ be the set of positive integers, and let $f:\mathbb N\to\mathbb N$ be a strictly increasing function such that $f(2)=2$ and $f(m)f(n)=f(mn)$ for all positive integers $m,...
Simply Beautiful Art's user avatar
6 votes

Why are induction proofs so challenging for students?

I found this post as a student trying to figure out why induction proofs are so difficult to understand. There are good answers here, but I think many are not specific enough to why induction proofs (...
conveniencesample's user avatar
6 votes

'Low-algebra' examples of induction

I am going to try the following activity as a first introduction to Mathematical Induction on Monday next week. I will let you know how it goes. The implication $P(k) \implies P(k+1)$ let's you "...
Steven Gubkin's user avatar
6 votes

Does induction really avoid proving an infinite number of claims?

The most basic way to prove a claim of the form $$\forall x \in X: P(x)$$ is universal generalization. Such a proof looks like this: Let $x \in X$ be chosen arbitrarily. Argue $P(x)$. This is a way ...
Steven Gubkin's user avatar
6 votes

Does a proof by induction have to explicitly refer to the principle of mathematical induction?

A blast from the past comment, for the consolation of your students, of a mathematician being marked down by one of the most influential mathematicians of his day: John Wallis in his Arithmetica ...
user1815's user avatar
  • 5,475
5 votes

Teaching strong induction instead of induction

I'm not sure how much this experience is worth, because it is such a different environment than the standard college proof environment, but the high school math program PROMYS does this. I believe ...
David E Speyer's user avatar
5 votes

Good, simple examples of induction?

For what natural $n$ does there exist a square composed of $n$ squares? Example: 1, 4, and 6 are valid, but one cannot construct a square from 2, 3, or 5 squares. Proof:
Simply Beautiful Art's user avatar
5 votes

Why do students only see the last term of a sum abbreviated with an ellipsis?

The other answers may indeed be right, but another thing just occurred to me, namely that when they prove the base case of the induction, the sum on the left-hand side does generally reduce to a ...
Mike Shulman's user avatar
  • 6,540
5 votes

Does a proof by induction have to explicitly refer to the principle of mathematical induction?

I am (one of the) colleagues David refers to in his post. The reason I am doing this lies in some of the answers/comments posted here already. For example, Humberto sais: "While technically it ...
Ferenc Beleznay's user avatar
4 votes

Is induction or recursion easier to understand?

As a disclaimer, I am a CS teacher, so I teach both concepts within that context. However, there is no doubt in my mind that induction is far harder for students to grasp. I have not been able to ...
Ben I.'s user avatar
  • 351
4 votes

'Low-algebra' examples of induction

I think tiling problems are good for this kind of thing. See, for example, this. There they describe how to prove the statement "if you have a $2^n\times 2^n$ chessboard with one square missing, ...
ncr's user avatar
  • 2,986

Only top scored, non community-wiki answers of a minimum length are eligible