Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [induction]

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 for questions about induction over natural numbers but is also appropriate for other kinds of induction such as transfinite, structural, double, backwards, etc.

Mathematical induction 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 relations which are well-founded, this tag is aimed mostly at questions about induction over natural numbers.

In general use, induction means inference from the particular to the general. This is used in terms such as inductive reasoning, which involves making an inference about the unknown based on some known sample. Mathematical induction is not true induction in this sense, but is rather a form of proof.

Induction over the natural numbers generally proceeds with a base case and an inductive step:

  • First prove the statement for the base case, which is usually $n=0$ or $n=1$.
  • Next, assume that the statement is true for an input $n$, and prove that it is true for the input $n+1$.

The following variant goes without a base case: Assuming the statement is true for all $n\in\mathbb N$ with $n < N$, prove that is true for $N$, too. This has to be done for all $N\in\mathbb N$.

10150 questions
6
votes
4 answers

Proof by Induction $n^2+n$ is even

I'm not entirely sure if I'm going about proving $n^2+n$ is even for all the natural numbers correctly. $P(n): = n^2+n$ $P(1) = 1^2+1 = 2 = 0$ (mod $2$), true for $P(1)$ Inductive step for $P(n+1)$: $\begin{align}P(n+1) &=&…
Robert
  • 165
6
votes
2 answers

Geometrical proof by induction

Given a segment $AB$ of length $1$, define the set $M$ of points in the following way: it contains the two points $A,B$ and also all points obtained from $A,B$ iterating the following rule: for every pair of points $X,Y$ in $M$, the set $M$ also…
user19405892
  • 15,592
6
votes
2 answers

Proof by induction that $\frac1{n+1}+ \frac1{n+2}+\cdots+\frac1{2n}=1-\frac{1}{2}+\cdots+\frac{1}{2n-1}-\frac{1}{2n}.$

Prove that for any positive integer, $$\frac1{n+1}+ \frac1{n+2}+\cdots+\frac1{2n} = \left(1-\frac1{2}\right)+\left(\frac1{3}-\frac1{4}\right)+\cdots+\left(\frac1{2n-1}-\frac1{2n}\right).$$ I have tried using a proof by induction but do not know how…
user222009
  • 63
6
votes
2 answers

Proof by induction: $(1+x)^n > 1 + nx+nx^2$

This is one of the exercises that appears in Apostol's Calculus I. I'm not sure whether what I did is correct. Let $n_1$ be the smallest positive integer $n$ for which the inequality $(1+x)^n > 1 + nx+nx^2$ is true for all $x > 0$. Compute $n_1$…
asd
  • 1,765
5
votes
2 answers

$n^{3} + 2n$ is divisible by $3$. Is this induction proof correct?

Question: Prove by means of the principle of induction that for every $n ∈ N$ the number $n^{3} + 2n$ is divisible by $3$. Proof Denote "$n^{3} + 2n$ is divisible by 3" by $P(n)$. Check $P(n)$ for an arbitrary $n$, for instance $n=1$.…
Sjoerd
  • 173
5
votes
5 answers

proof by induction - explanation on it

Proof by induction. It's pretty useful, and the purpose of it makes a lot of sense. However one thing has always bothered me concerning it. So when you apply induction, one has a base case where you choose a case and apply it to show it works. But…
Nick Freeman
  • 987
5
votes
2 answers

How Many Miles to Retrieve an Object N Miles into a Desert?

The problem: Suppose that you are interested in retrieving an object located in the middle of the desert, n kilometers away. Your car can carry enough fuel to travel 3 kilometers, and you have an unlimited supply of spare fuel tanks which you can…
user82004
5
votes
3 answers

Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers?

I am referring to the part of proof by mathematical induction where you show that "if it is true for one value k then it is true for the value k+1". Does proof by induction work over all real numbers? I mean by considering any arbitrary change, say…
Tom
  • 53
5
votes
5 answers

Prove that the inequality $(1+ \frac{1}{n})^n < n$ holds for all $n \geq 3$

First we need to prove the basis. If we let $n=3$, then $(1+ \frac{1}{3})^3 < 3$ $(\frac{3}{3}+ \frac{1}{3})^3 < 3$ $(\frac{4}{3})^3 < 3$ $(\frac{64}{27}) < 3$ The inequality statement is true For $P(n), (1+ \frac{1}{n})^n < n$ We assume that…
usukidoll
  • 2,074
5
votes
2 answers

Induction: show that $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$

The question: Induction: show that: $$1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \frac{1}{\sqrt{4}} + ... + \frac{1}{\sqrt{n}} < 2\sqrt{n}$$ for $n \geq 1$ My attempt at a solution: First we test the base case: $n=1$ this gives us: $$1 <…
Lukas Arvidsson
  • 2,376
5
votes
5 answers

Proving with Induction When The Claim Fails For Several Numbers

I want to find for what positive integers n, the statement $11n+17 \leq 2^n$ is true. I then want to prove that this is true with induction. The problem I see here, is that to prove it, I need to find P(1), which gives $11+17\leq2$, which is false.
Matt
  • 155
5
votes
3 answers

$\text{Prove}\left( 1-\frac{1}{\sqrt{2}} \right)...\left( 1-\frac{1}{\sqrt{n}} \right)\lt \frac{2}{n^{2}}\text{ for }n\ge 2$

I'm completely lost on this question: $$\text{Prove}\left( 1-\frac{1}{\sqrt{2}} \right)\left( 1-\frac{1}{\sqrt{3}} \right)...\left( 1-\frac{1}{\sqrt{n}} \right)\lt \frac{2}{n^{2}} \text{ for }n\ge 2$$ alternatively, $$\prod_{a=2}^{n}…
lkc36
  • 53
5
votes
12 answers

Complete induction of $10^n \equiv (-1)^n \pmod{11}$

To prove $10^n \equiv (-1)^n\pmod{11}$, $n\geq 0$, I started an induction. It's $$11|((-1)^n - 10^n) \Longrightarrow (-1)^n -10^n = k*11,\quad k \in \mathbb{Z}. $$ For $n = 0$: $$ (-1)^0 - (10)^0 = 0*11 $$ $n\Rightarrow n+1$ $$\begin{align*} (-1)…
Igor
  • 51
5
votes
6 answers

Proof by induction: Show that $7|5^{2n}-2^{5n}$

I'm stuck on my inductive step, and can't figure out how to manipulate this algebraically to get the form that I want... $5^{2k}-2^{5k}=7m,m\in\mathbb{Z}$ \begin{align*} 5^{2k+2}-2^{5k+2}=5^{2k}\cdot 5^{2}-2^{5k}\cdot 2^{2} \end{align*} So i'm not…
Mirrana
  • 9,009
1 2 3
…
99 100