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
4
votes
4 answers

How do I prove by induction that, for $n≥1, \sum_{r=1}^n \frac{1}{r(r+1)}=\frac{n}{n+1}$?

Hi can you help me solve this: I have proved that $p(1)$ is true and am now assuming that $p(k)$ is true. I just don't know how to show $p(k+1)$ for both sides?
maxmitch
  • 651
4
votes
3 answers

There is no rational number r with the property $r^2 =3$

There is no rational number r with the property $r^2 =3$ This is what I did. Proof by contradiction. Assume that there exist a rational number $r=a/b$ where $a$ and $b$ are integers. This implies that: \begin{align*} r^2 & = 3\\ (a/b)^2 &=3 \\…
John
  • 41
4
votes
2 answers

Use mathematical induction to prove that for all integers $n \geq 4, 3^n \geq n^3$

Use mathematical induction to prove that for all integers $n \geq 4, 3^n \geq n^3$ So with this question I'd check the base case. Suppose $P(4)$ is the predicate $3^4 \geq 4^3$, where $n \geq 4$ $81 \geq 64$, therefore $P(4)$ is true. Suppose $P(k)$…
99 Fishing
  • 245
4
votes
2 answers

Proving by induction that $| x_1 + x_2 + ... + x_n | \leq | x_1 | + | x_2| + ... + | x_n |$

This is the first question in Thomas' Calculus Appendix on Proof by Induction Exercise (Exercise A.1). As the title suggests, I'd like to prove by induction that $| x_1 + x_2 + ... + x_n | \leq | x_1 | + | x_2| + \ldots + | x_n |$ is true for any n…
Jake Hendy
  • 73
  • 1
  • 6
4
votes
2 answers

Proof by induction regarding injections and part of the pigeonhole principle

Prove the following implication by induction on $m$: If there exists an injection $N_m \rightarrow N_n$, then $m \le n$. $N_n$ and $N_m$ are sets with $n$ and $m$ elements, respectively. I know how to do proofs by induction, I'm just struggling…
user1356910
  • 41
4
votes
3 answers

Math induction ($n^2 \leq n!$) help please

I'm having trouble with a math induction problem. I've been doing other proofs (summations of the integers etc) but I just can't seem to get my head around this. Q. Prove using induction that $n^2 \leq n!$ So, assume that $P(k)$ is true: $k^2…
Jason Byrne
  • 51
  • 1
4
votes
4 answers

Prove by induction that $n^3 < 3^n$

The question is prove by induction that $n^3 < 3^n$ for all $n\ge4$. The way I have been presented a solution is to consider: $$\frac{(d+1)^3}{d^3} = (1 + \frac{1}{d})^3 \ge (1.25)^3 = (\frac{5}{4})^3 = \frac{125}{64} <2 < 3$$ Then using this…
user258521
  • 1,001
4
votes
2 answers

Induction with Inequalities

Suppose that we are trying to prove that $2^n > 10n + 9 $ $\forall n \geq 9$ Basis: $2^9 > 99$ is true. Inductive Hypothesis: Assume that it is true that $n=k$ $\forall n \geq 9$ Then: $2^k > 10k + 9 $ Inductive step: Prove for $n=k+1$: $$2^{(k+1)}…
RedShift
  • 765
  • 3
  • 11
  • 28
4
votes
3 answers

Prove by induction that $ 2!4!..(2n)! > ((n+1)!)^n $

Prove by induction that $ 2!4!..(2n)! > ((n+1)!)^n $. Attempt : It is clearly true for $n=2$. Let it be true for $n=m$. Therefore, $ 2!4!..(2m)! > ((m+1)!)^m $ => $ 2!4!..(2m)!(2(m+1))! > ((m+1)!)^m . {2(m+1)}! $ It will be done if I can prove…
user354595
  • 189
4
votes
1 answer

Ackermann-Péter Function: Proof by induction that A(x,y) < A(x,y+1)

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ I want to prove by induction over x that $$A(x,y) < A(x,y+1) \; \forall x,y \in \mathbb{N} $$ Basis: $x = 0$ $$ A(0,y) = y+1 < y+2 =…
muffel
  • 2,879
4
votes
2 answers

Proving $3^n \geq 3n$ using mathematical induction

So I have to prove that $3^n$ is greater than or equal to $3n$ using induction. The base case is a not a problem, but I can't seem to figure out where to go for $(n-1)$. I've tried saying: $$3^n=3\cdot3^{n-1}>3\cdot3(n-1)$$ $$3\cdot3(n-1)=9n-9$$ I'm…
PJ Johnson
  • 107
4
votes
4 answers

Prove by induction that $n^2 < 2^n$ for all $n \geq 5$?

So far I have this: First consider $n = 5$. In this case $(5)^2 < 2^5$, or $25 < 32$. So the inequality holds for $n = 5$. Next, suppose that $n^2 < 2^n$ and $n \geq 5$. Now I have to prove that $(n+1)^2 < 2^{(n+1)}$. So I started with $(n+1)^2 =…
Chris
  • 1,129
  • 1
  • 9
  • 18
4
votes
3 answers

Prove $3^n > n^2$ by induction

Prove that $$3^n > n^2$$ I am using induction and I understand that when $n=1$ it is true. The induction hypothesis is when $n=k$ so $3^k>k^2$. So for the induction step we have $n=k+1$ so $3^{k+1} > (k+1)^2$ which is equal to $3\cdot3^k >…
bella
  • 121
4
votes
3 answers

Why does induction prove equality?

I know how to prove equality for my homework assignment, but I can't understand why it actually proves that equality. Could you please explain?
hey
  • 209
4
votes
3 answers

How do I derive a formula for this ∏ notation?

For $n\in\Bbb N$ and $n\ge 2$, find and prove a formula for $\prod_{i=2}^n\left(1-\frac1{i^2}\right)$. I can easily prove the formula using induction once I have the equivalent result but I'm having a bit of trouble actually finding said formula.…
Arsala Bangash
  • 153
1 2 3
…
99 100