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
0
votes
3 answers

question on prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$

I have to prove by induction that for each n$\in\mathbb{N}_{\ge2}$, $n^2$< $n^3$. If I try to prove for P(1) I end up with 1 < 1. Is this right? Why does it or does it not make sense?
ajs512
  • 471
0
votes
1 answer

prove or disprove $n > 0 ~\rightarrow~\prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ \frac{1}{(2n~+~2)!}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n > 0 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ \frac{1}{(2n~+~2)!} $$ And i am not clear whether it should be…
user117911
  • 89
0
votes
2 answers

Induction Question. Suppose there are n teams in a football league

how can i prove this Let n > 1 be an integer. Suppose there are n teams in a football league and every two teams have played against each other exactly once with no ties. Prove that it is possible to number the teams 1 to n such that at the end of…
funky-nd
  • 111
0
votes
2 answers

Mathematical Induction - condition

Question: Prove that $n(n+1)(n+5)$ is always divisible by 3 using mathematical induction. Well it is quite obvious that P(1) is true. However, my question is if: $$3\lambda\frac{(k+2)(k+6)}{k(k+5)}$$ Is enough of a condition to prove that it's…
Gummy bears
  • 3,408
0
votes
2 answers

Proof by Induction (concerning $3^n\ge1+2n$)

I've been able to follow the idea and steps of induction so far but I've hit a road block in understanding one of the examples in a text book. This is what the book says p.97: Prove: $3^n \geq1 + 2n$ Skipping past the base case and assuming it's…
xlm
  • 333
0
votes
2 answers

Prove $(bab^{-1})^n = ba^nb^{-1}$ by induction

p(1): $(bab^{-1})^1 = ba^1b^{-1}.$ p(k + 1): $(bab^{-1})^{k + 1} = (bab^{-1})^k(bab^{-1}) = b^ka^kb^{-k}bab^{-1} = ba^{k + 1}b^{-1}.$ Would that work?
Marko
  • 97
0
votes
2 answers

Prove that $n < 2^n$ for all n holds N.

Prove that $n < 2^n$ for all $n ∈ N$. By induction. I know how simple is this, but could anyone help and give detailed explanation? Edit: Its $2^n$ NOT 2n
Mohamed
  • 183
0
votes
3 answers

Does Induction theorem fails here at Euler's conjecture?

I read in a Book written by Raymond A. Barnett and Micheal R. Ziegler the way to prove conjectures for infinite members of a given set and that is, Mathematical Induction. When I read Induction, I found it very interesting. The way to prove…
Sufyan Naeem
  • 2,298
0
votes
4 answers

I'm having trouble understanding a step of induction.

The problem my teacher presented was to prove, $(1 + x)^n \geq 1 + nx$ for all real numbers $x > -1$ and integers $n \geq 2$. The way it was done in class is: $(1+nx)(1+x) ≤ (1+x)^n (1+x) $ $1 + x + nx + nx^2 ≤ (1+x)^{n+1}$ $1 + x + nx +…
John
  • 71
0
votes
1 answer

On proving a statement is true by induction

We prove $\sum_{i=1}^{n} x^3 = (1+2+\cdots+n)^2$. We observe that this expression is true for $ n=1$. Now assume this is already true; we prove it for $\sum_{i=1}^{n+1} x^3 = (1+2+\cdots+n+n+1)^2$. We note that the expression in the inside of the…
Don Larynx
  • 4,703
0
votes
1 answer

Induction - Prime Numbers

Prove that, for every natural number $n > 2$, there is a prime number between $n$ and $n!$. [Hint: There is a prime number that divides $n! - 1$.]
Anonymous
  • 77
0
votes
1 answer

Mathematical induction

I've already proven the first part but in (ii) I managed to get until $u_{n+1} = \sqrt{9-\epsilon} - 1$ I don't know how to show the approximation answer.
space monkeys
  • 97
0
votes
3 answers

Proof by induction

This is a topic I always struggle with. Could someone help me prove this: Prove by induction: $$ \sum_{k=1}^n 2k = n^2 + n, $$ Thanks for any help
Raj
  • 1
0
votes
3 answers

Mathematical induction with binomial coefficients

I am trying to prove the following equation using mathematical induction: $$\sum \binom{n}{k}2^k = 3^n.$$ I am able to prove a similar induction without the $2^k$ on the left side and with $ 2^n $ on the right side, but I think this is probably a…
milan
  • 11
0
votes
2 answers

Prove by induction that $\sum^{n}_{k=1}5k-4=\frac12n(5n-3)$ is true for $n\ge 1$

Prove by induction that the following equation is true for $n\ge1$ $$\sum^{n}_{k=1}5k-4=\frac12n(5n-3)$$ I did the following: $$\sum^{1}_{\color{blue}{k}=1}5\color{blue}{k}-4\rightarrow5\cdot\color{blue}{1}-4=1$$ $\color{red}{n}=1$,…
Adnan
  • 1,021
1 2 3
…
99
100