For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

68
votes
9answers
10k views

Surprise exam paradox?

I just remembered about a problem/paradox I read years ago in the fun section of the newspaper, which has had me wondering often times. The problem is as follows: A maths teacher says to the class ...
62
votes
6answers
6k views

Induction on Real Numbers

One of my Fellows asked me whether total induction is applicable to real numbers, too ( or at least all real numbers ≥ 0) . We only used that for natural numbers so far. Of course you have to change ...
50
votes
12answers
5k views

All natural numbers are equal.

I saw the following "theorem" and its "proof". I can't explain well why the argument is wrong. Could you give me clear explanation so that kids can understand. Theorem: All natural numbers are ...
46
votes
2answers
3k views

Proof of 1 = 0 by Mathematical Induction on Limits?

I got stuck with a problem that pop up in my mind while learning limits. I am still a high school student. Define $P(m)$ to be the statement: $\quad ...
44
votes
12answers
6k views

Proof that every number ≥ $8$ can be represented by a sum of fives and threes.

Can you check if my proof is right? Theorem. $\forall x\geq8, x$ can be represented by $5a + 3b$ where $a,b \in \mathbb{N}$. Base case(s): $x=8 = 3\cdot1 + 5\cdot1 \quad \checkmark\\ x=9 = 3\cdot3 ...
40
votes
9answers
1k views

Fake induction proofs

Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do ...
37
votes
10answers
5k views

Good examples of double induction

I'm looking for good examples where double induction is necessary. What I mean by double induction is induction on $\omega^2$. These are intended as examples in an "Automatas and Formal Languages" ...
36
votes
26answers
4k views

How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of ...
33
votes
18answers
7k views

Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ ...
33
votes
5answers
4k views

Prove that the 25 people can be seated in this way

5 mathematicians, 5 biologists, 5 chemists, 5 physicists, and 5 economists sit around a large round table. Prove that the 25 people can be seated such that, if A and B are two different people with ...
32
votes
5answers
3k views

Dominoes and induction, or how does induction work?

I've never really understood why math induction is supposed to work. You have these 3 steps: Prove true for base case (n=0 or 1 or whatever) Assume true for n=k. Call this the induction ...
30
votes
14answers
4k views

Why doesn't mathematical induction work backwards or with increments other than 1?

From my understanding of my topic, if a statement is true for $n = 1,$ and you assume a statement is true for arbitrary integer $k$ and show that the statement is also true for $k + 1,$ then you prove ...
30
votes
7answers
2k views

Must we use induction to prove a statement for all integers

This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction. From Bill's answer: A proof that a ...
29
votes
4answers
2k views

Avoiding proof by induction

Proofs that proceed by induction are almost always unsatisfying to me. They do not seem to deepen understanding, I would describe something that is true by induction as being "true by a technicality". ...
25
votes
13answers
703 views

Examples where it is easier to prove more than less

Especially (but not only) in the case of induction proofs, it happens that a stronger claim $B$ is easier to prove than the intended claim $A$ (e.g. since the induction hypothesis gives you more ...
25
votes
7answers
7k views

Is there no solution to the blue-eyed islander puzzle?

Text below copied from here The Blue-Eyed Islander problem is one of my favorites. You can read about it here on Terry Tao's website, along with some discussion. I'll copy the problem here as ...
24
votes
4answers
1k views

Why is “mathematical induction” called “mathematical”?

One of my whims is that I never write "mathematical induction" but just "induction". We are doing maths, so what is the point about precising? We don't say "Let $f$ be a mathematical function from the ...
23
votes
5answers
2k views

What makes induction a valid proof technique?

What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for ...
22
votes
7answers
4k views

Why $a^n - b^n$ is divisible by $a-b$?

I did some mathematical induction problems on divisibility $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5. Can these be generalized as $a^n$ ...
22
votes
6answers
885 views

IMO 1987 - function

Show that there is no function $f: \mathbb{N} \to \mathbb{N}$ such that $f(f(n))=n+1987, \ \forall n \in \mathbb{N}$.
21
votes
3answers
618 views

A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling ...
21
votes
5answers
904 views

How does one actually show from associativity that one can drop parentheses?

I've always heard this reasoning, and it makes obvious sense, but how do you actually show it for some arbitrary product? Would it be something like this? ...
21
votes
7answers
577 views

Illustrative examples of a phenomenon in the logic of mathematical induction

It is said (and I myself have said) that in some cases the easiest way to prove a statement by mathematical induction is to prove a stronger statement by mathematical induction, because then one has a ...
20
votes
6answers
2k views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
18
votes
9answers
1k views

What is the purpose of the first test in an inductive proof?

Learning about proof by induction, I take it that the first step is always something like "test if the proposition holds for $n = \textrm{[the minimum value]}$" Like this: Prove that ...
18
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
18
votes
5answers
2k views

Why doesn't induction extend to infinity? (re: Fourier series)

While reading some things about analytic functions earlier tonight it came to my attention that Fourier series are not necessarily analytic. I used to think one could prove that they are analytic ...
18
votes
3answers
841 views

My first induction proof (very simple number theory). Please mark/grade.

What do you think about my first induction proof? Please mark/grade. Theorem The sum of the cubes of three consecutive natural numbers is a multiple of 9. Proof First, introducing a predicate ...
17
votes
12answers
3k views

Prove that $ n < 2^{n}$ for all natural numbers $n$.

Prove that $ n < 2^{n} $ for all natural numbers $n$. I tried this with induction: Inequality clearly holds when $n=1$. Supposing that when $n=k$, $k<2^{k}$. Considering $k+1 <2^{k}+1$, ...
17
votes
9answers
2k views

There are no bearded men in the world - What goes wrong in this proof?

Several years ago in a textbook I read this example as a faulty use of proof by induction. I never really realized why it fails. Here it goes: Theorem. There are no bearded men in the world. ...
17
votes
6answers
3k views

Why is mathematical induction a valid proof technique?

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ...
16
votes
6answers
971 views

What are some examples of induction where the base case is difficult but the inductive step is trivial?

According to Wikipedia: ...proofs by mathematical induction have two parts: the "base case" that shows that the theorem is true for a particular initial value such as n = 0 or n = 1 and ...
15
votes
3answers
2k views

Proof that $\pi$ is rational

I stumbled upon this proof of $\pi$ being rational (coincidentally, it's Pi Day). Of course I know that $\pi$ is irrational and there have been multiple proofs of this, but I can't seem to see a flaw ...
14
votes
5answers
444 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
14
votes
2answers
518 views

Prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction.

Problem: prove $\sqrt{2\sqrt{3\sqrt{\cdots\sqrt{n}}}}<3$ by induction. I tried some, but stopped in $\sqrt[2^n]{n+1}$. Also tried with $2\sqrt{3\cdots}<3^2$ and so on.
14
votes
6answers
588 views

Fascinating induction problem with numerous interpretations

Problem: Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile, ...
13
votes
11answers
4k views

Prove that $1 + 4 + 7 + · · · + 3n − 2 = \frac {n(3n − 1)}{2}$

Prove that $$1 + 4 + 7 + · · · + 3n − 2 = \frac{n(3n − 1)} 2$$ for all positive integers $n$. Proof: $$1+4+7+\ldots +3(k+1)-2= \frac{(k + 1)[3(k+1)+1]}2$$ $$\frac{(k + 1)[3(k+1)+1]}2 + ...
13
votes
6answers
418 views

Show that $n \ge \sqrt{n+1}+\sqrt{n}$

(how) Can I show that: $n \ge \sqrt{n+1}+\sqrt{n}$ ? It should be true for all $n \ge 5$. Tried it via induction: $n=5$: $5 \ge \sqrt{5} + \sqrt{6} $ is true. $n\implies n+1$: I need to show ...
13
votes
6answers
1k views

How do you prove that proof by induction is a proof?

Are proofs by induction limited to cases where there is an explicit dependance on a integer, like sums? I cannot grasp the idea of induction being a proof in less explicit cases. What if you have a ...
13
votes
4answers
228 views

Proving $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$ by induction

How can I prove by induction that $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$? My guess is that there must be another form to express the sum of nested square roots, but I don't know how ...
13
votes
2answers
987 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
13
votes
2answers
3k views

What is complete induction, by example? $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$

So, I've been revising for an exam and I came up against the question " prove $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$. Now, I know how to do this. If I assume $n=k$ divisible by $7$, ...
13
votes
1answer
331 views

Prove $\sin(1/n)<1/n$ for all $n$

I need to prove $\sin(1/n)<1/n$ for all $n \in \Bbb N$ using mathematical induction. Dont know how to start. Please help!
12
votes
6answers
717 views

Induction - Examples where the induction step is correct but the base case is always wrong [duplicate]

I'd like to present to my students some induction examples that always satisfy the inductive step but never the base case. It could be for natural numbers, graphs or anything else.
12
votes
4answers
3k views

Solve by induction: $n!>(n/e)^n$

To Prove : $n! > (n/e)^n$ The question seems easy but it ain't; anyone up for it ?
12
votes
11answers
14k views

Proof that $n^3+2n$ is divisible by 3

I'm trying to freshen up for school in another month, and I'm struggling with the simplest of proofs! Problem: For any natural number n , n3 + 2n is divisible by 3. This makes sense ...
12
votes
2answers
722 views

Inverted induction

I am working on a proof, and to do it, I think it would be optimally to use induction backwards. Show that 1 doesn't work. Assume n doesn't work. Prove that n+1 doesn't work. Is this valid?
12
votes
5answers
241 views

Show that $({\sqrt{2}\!+\!1})^{1/n} \!+ ({\sqrt{2}\!-\!1})^{1/n}\!\not\in\mathbb Q$

How could we prove that for every positive integer $n$, the number $$({\sqrt{2}+1})^{1/n} + ({\sqrt{2}-1})^{1/n}$$ is irrational? I think it could be done inductively from a more general ...
12
votes
8answers
779 views

prove $\frac{1}{ n+1}+\frac{1}{ n+2}+\cdots+\frac{1}{2n}<\frac{25}{36}$ by mathematical induction

How to prove $$\frac{1}{ n+1}+\frac{1}{ n+2}+\cdots+\frac{1}{2n}<\frac{25}{36}$$ by Mathematical induction,n$\ge $1
12
votes
2answers
194 views

prove $\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{k!}$

i am learning maths so fast here in MSE, thank you guys so much for being here to help us! so now, my next step towards proficiency: :). i am trying to prove that ...