Skip to main content
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
13 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
  • 390
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,594
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

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
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,318
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
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
  • 390
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

'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

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

How about: A tree with $n\ge 1$ vertices has $n-1$ edges.
Aeryk's user avatar
  • 8,019
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

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,778
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

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
  • 361
4 votes

Does induction really avoid proving an infinite number of claims?

I guess what I dislike about the characterization of induction quoted in the OP is that it takes a statement $\forall n.T(n)$ about natural numbers, separates it into a sequence of statements $T(1)$, $...
user1815's user avatar
  • 5,778
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
4 votes

'Low-algebra' examples of induction

A couple of simple examples come to mind: 1) Prove that there are $2^n$ subsets of an $n$-element set. 2) Prove the power rule of derivatives for non-negative integer powers using the product rule.
John Coleman's user avatar
  • 1,536
4 votes

Good, simple examples of induction?

I often teach a short unit on induction in elementary calculus classes—it comes up very naturally when trying to prove a version of the power rule (i.e. the version pertaining to functions of the form ...
Xander Henderson's user avatar
  • 8,288
3 votes

Good, simple examples of induction?

Hmm, I'm surprised than no one mentioned de Moivre's formula: $$(\cos \phi +i\cdot \sin \phi)^n= \cos (n\phi) + i\cdot\sin (n\phi)$$ It is an excellent exercise to prove it. We must also use the ...
nonuser's user avatar
  • 390
3 votes

Teaching strong induction instead of induction

Note that the "strong induction" is not even the most general induction scheme you can design. A high school level example is the proof of the AM-GM inequality for $n$ positive numbers where ...
fedja's user avatar
  • 3,939
3 votes

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

Typically you want to name things. This makes them visible and something you can discuss. So, while teaching, you do want to say that this thing her is induction, so we have to remember to check the ...
Tommi's user avatar
  • 7,374
3 votes

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

In a pedagogical context I can see four types of situation where it may reasonably be required for students to explicitly state their use of the principle of mathematical induction: If writing proofs ...
Yiab's user avatar
  • 31
3 votes

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

Peano's axioms without the axiom of induction has some models that do not correspond to the natural numbers that we have in our minds. In order to prove that every natural number $n$ other than $0$ ...
user52817's user avatar
  • 11k
3 votes

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

Let's not overlook an obvious application of induction is to turn it around and go from general to specific. Let's say we have established $H(1)$ and that $H(k+1)$ follows from $H(k)$ and we are ...
user52817's user avatar
  • 11k
3 votes

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

To be a proof, an argument needs to be explicit about the logical structure. An induction proof won't be any different. Take a very standard task like: such as showing that, for all $n\in \mathbb{N}$...
Louis's user avatar
  • 131

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