Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

59
votes
8answers
9k 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 ...
53
votes
6answers
5k 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 ...
49
votes
12answers
4k 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 ...
44
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 ...
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 ...
36
votes
10answers
4k 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" ...
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 ...
31
votes
17answers
6k 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$ ...
29
votes
5answers
2k 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 ...
29
votes
7answers
1k 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 ...
28
votes
13answers
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 ...
25
votes
7answers
6k 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 ...
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 ...
21
votes
5answers
3k 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$ ...
21
votes
8answers
385 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 ...
21
votes
7answers
520 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
5answers
821 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? ...
19
votes
5answers
694 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}$.
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
3answers
772 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
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 ...
17
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 ...
17
votes
3answers
515 views

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

So I'm a bit stuck on the following problem I'm attempting. 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 with some ...
16
votes
12answers
2k 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$, ...
16
votes
8answers
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. ...
16
votes
6answers
877 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
1k 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
2answers
476 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.
13
votes
6answers
404 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
941 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
5answers
414 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 ...
13
votes
2answers
3k views

What is complete induction, by example?

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
307 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
11answers
11k 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
5answers
721 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
12
votes
8answers
730 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
185 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 ...
12
votes
5answers
245 views

How to prove $n < \left(1+\frac{1}{\sqrt{n}}\right)^n$

I want to know how to prove the following inequality. For $n = 1, 2, 3, \ldots $ $$ n < \left(1+\frac{1}{\sqrt{n}} \right)^n $$ I tried with math induction but I failed.
12
votes
2answers
767 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 ...
11
votes
6answers
3k views

Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. ...
11
votes
6answers
2k views

Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$$ ...
11
votes
4answers
2k 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 ?
11
votes
10answers
372 views

Prove by induction that for all $n \geq 3$: $n^{n+1} > (n+1)^n$

I am currently helping a friend of mine with his preperations for his next exam. A big topic of the exam will be induction, thus I told him he should practice this a lot. As at the beginning he had no ...
11
votes
3answers
344 views

Irrationality of $\sqrt 2$ using induction

I came upon this exercise in a textbook. I know that $\frac{n}{b} \ne \sqrt{2} $ for all $b \gt 0$ and $n \le N_0$. How can I then show that $\frac{N_0 + 1}{b} \ne \sqrt{2}$ for all $b \gt 0$?
11
votes
4answers
188 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 ...
11
votes
1answer
329 views

An inequality $\,\, (1+1/n)^n<3-1/n \,$using mathematical induction

It was shown in here that $\left(1+\frac{1}{n}\right)^n < n$ for $n>3$. I think we can be come up with a better bound, as follows: $$\left(1+\frac{1}{n}\right)^n \le 3-\frac{1}{n}$$ for ...
11
votes
2answers
833 views

Beginner - Mathematical induction - help understanding example?

So: $$ (1+x)^n ≥ 1 + nx $$ So he checks for 1, and get: $$ 1+x ≥ 1+x $$ Next for variable k: $$ (1+x)^k ≥ 1 + kx $$ Then the book wanna prove: $$ (1+x)^{k+1} ≥ 1 + (k + 1)x $$ And here ...
11
votes
3answers
153 views

$1!+2!+\ldots+n!$ cannot be the square of a positive integer

I have to prove that $1!+2!+\ldots+n!$ cannot be the square of a positive integer, $\forall n\geq4$. I've tried to do this with induction, but I don't seem to reach any satisfactory conclusion. Any ...
11
votes
1answer
151 views

A Fantabulous integer is an integer which has another fantabulous integer smaller than it

BdMO 2013 problem-7: A positive integer is called “Fantabulous” if there is another fantabulous positive integer smaller than it. Find the number of fantabulous integers. I am bamboozled at ...
10
votes
4answers
2k views

What is the second principle of finite induction?

I understand the principle of finite induction, but my book then mentions that there is a variant of the first where requirement b is changed to If k is a positive integer such that 1,2...,k ...