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

55
votes
7answers
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 ...
51
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 ...
46
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 ...
43
votes
2answers
2k 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
3k 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
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" ...
29
votes
17answers
5k 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 ...
28
votes
13answers
3k 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 ...
27
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 ...
19
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$ ...
19
votes
7answers
474 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 ...
18
votes
5answers
749 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? ...
18
votes
5answers
640 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}$.
17
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: ...
17
votes
6answers
4k 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 ...
17
votes
3answers
710 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 ...
16
votes
3answers
505 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 ...
15
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 ...
15
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$, ...
15
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. ...
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
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 ...
14
votes
3answers
1k 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 ...
14
votes
5answers
821 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 ...
12
votes
6answers
396 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 ...
12
votes
5answers
383 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 ...
12
votes
2answers
454 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.
12
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$, ...
12
votes
1answer
291 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!
11
votes
6answers
865 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 ...
11
votes
8answers
675 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
11
votes
2answers
180 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 ...
11
votes
2answers
658 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 ...
10
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 ?
10
votes
10answers
325 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 ...
10
votes
11answers
9k 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 ...
10
votes
3answers
317 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$?
10
votes
4answers
523 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
10
votes
1answer
253 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 ...
10
votes
2answers
777 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 ...
10
votes
3answers
138 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 ...
10
votes
1answer
136 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 ...
9
votes
6answers
1k 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}}$$ ...
9
votes
2answers
154 views

Proving that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$

How do I prove that: $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$$ Do I use induction?
9
votes
4answers
229 views

Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
9
votes
1answer
106 views

Minimum number of hemispheres covering a sphere

Here is a question which seems easy but seems to have many pitfalls. If I give you an arbitrary covering of the sphere by $N$ closed hemispheres. You can pick any of the hemispheres to keep. What is ...
9
votes
2answers
300 views

What's an induction problem that will be hard to answer with “backwards reasoning?”

I'm currently the teaching assistant for a course that serves as an introduction to rigorous proofs, and I've noticed some of my students have a tendency to try and use a sort of "backwards reasoning" ...
8
votes
6answers
2k 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. ...
8
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 ...