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
2
votes
1 answer

Division of a Particle

At time 0, a particle resides at the point 0 on the real line. Within 1 second, it divides into 2 particles that fly in opposite directions and stop at distance 1 from the original particle. Within the next second, each of these particles again…
Kushagra Chatterjee
  • 87
2
votes
1 answer

Prove using induction that involves floor

Define $\ \mathcal T(n) $ recursively by $\ \mathcal T(0) = 1, ~T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/3 \rfloor ) $ for $n \gt 0$. Prove by induction that $\ \mathcal T(n) \le n + 1 $ for every $\ n \in \mathbb N $. I'm not quite sure how to…
Ray.R.Chua
  • 273
2
votes
2 answers

Concrete Mathematics: how to prove 1.14 using induction

In chapter 1, (1.14), the authors uses induction to prove $A(n) = 2^m$ where $$ \begin{eqnarray} A(1) & = & 1 \\ A(2n) & = & 2A(n), \text{for } n \ge 1 \\ A(2n + 1) & = & 2A(n), \text{for } n \ge 1 \\ \end{eqnarray}$$ As usual, $n = 2^m + 1$ and $0…
cinsk
  • 123
2
votes
0 answers

monotonicity proof - double induction

Suppose we have 4 functions depending on a variable $x$ : $a(x), b(x), c(x)$ and $d(x)$. I want to prove that $a(x) - c(x)$ is monotonically increasing in $x$, by an induction argument. Also I want to as well prove the same result for $b(x) -…
Roark
  • 233
2
votes
2 answers

Proof by Induction: $∀n ≥ 5, 2^n + 2n < n!$

I'm having trouble understanding how to solve this question. Proof by induction: $∀n ≥ 5, 2^n + 2n < n!$ I don't understand how they got those steps that I highlighted in the picture attached below. Any help is appreciated. Thanks!
ThunderBase
  • 21
2
votes
2 answers

Induction proof for stirling of first kind.

I have to show that for every stirling number of the first kind $\forall n \geq 2 : s_{n,n-2} = \frac{1}{24}n(n-1)(n-2)(3n-1) $ is true. I've started like this: Base case: Let $n$ be $n=2$, then per defintion $s_{n,0} = 0$. Since we have $s_{2,2-2}…
D idsea J
  • 151
  • 1
  • 9
2
votes
6 answers

Proof by mathematical induction that, for all non-negative integers $n$, $7^{2n+1} + 5^{n+3}$ is divisible by $44$.

I have been trying to solve this problem, but I have not been able to figure it out using any simple techniques. Would someone give me the ropes please? Prove for $n=1$ $7^3 + 5^4 = 968 = 44(22)$ Assume $F(k)$ is true and try $F(k+1)+-F(k)$ $F(k) =…
Adam Páltik
  • 316
2
votes
1 answer

Use complete induction to prove that $a_n < 2^n$ for every integer $n \geq 2$

Define the sequence of integers $a_0, a_1, a_2, \cdots$ as follows $$ a_i = \begin{cases} i+1 & 0 \leq i \leq 2 \\ a_{i-1} + a_{i-2} + 2a_{i-3} & i > 2 \\ \end{cases} $$ Use complete induction to prove that $a_n < 2^n$ for every…
Tree Garen
  • 709
  • 5
  • 15
2
votes
1 answer

Is this induction proof mathematically correct?

Proof that $\frac{n^3}{3} < 3n-3$ is true for $n=2$ but false for every other $ n \in \mathbb{N}$. Idea is to proof that $\frac{n^3}{3} \geq 3n-3$. Let $n$ be $n=3$ $\frac{27}{3} \geq 9-3 $. That means $\exists n \in \mathbb{N}$ such that…
D idsea J
  • 151
  • 1
  • 9
2
votes
5 answers

Show that $n^n>(n+1)!$ for all $n\ge3$

Show that $n^n>(n+1)!$ for all $n\ge3$ For $n=3$ it is to prove. assumed it true for some fixed $n\in \mathbb{N}$. Then tried to prove for $n+1$ $(n+1)^{n+1}=(n+1)^n(n+1)>n^n(n+1)>(n+1)!(n+1)$ Got stuck.
L praveen kumar
  • 33
2
votes
0 answers

recursive induction regarding two recursive functions

Consider the following recursive definitions of two functions from $\mathbb N \to \mathbb N$ $$ F(n) = \begin{cases} 1 & n = 0 \\ 2 & n = 1 \\ F(n-2)^2 \cdot F(n-1) & n > 1 \end{cases} $$ $$ G(n) = \begin{cases} 1 & n =…
Tree Garen
  • 709
  • 5
  • 15
2
votes
2 answers

Mathematical induction exercises

The exercise goes like this: Prove that the statement P(n) $n^2 + 3*n + 1$ is even always fails. My question is if it is sufficient to show that the base case fails for some of the first terms, or is that too trivial and I have to show that it…
Allorja
  • 303
2
votes
0 answers

Induction. A circle with n fuel tanks.

Problem: The sides of a circular track contain a sequence of cans of gasoline. The total amount in the cans is sufficient to enable a certain car to make one complete circuit of the track, and it could all fit into the car's gas tank at one time.…
Leo Tan
  • 21
2
votes
5 answers

Prove $u_n$ = $n$ $*$ $2^n$ with mathematical induction

I need to prove that $u_n$ = $n \times 2^n$ using mathematical induction with the below information. $u_1\;=\;2\;\text{ and }\;\;u_{n+1}=2\left(u_n+\frac{u_n}n\right)\;\text{ for }\;n\geq1$ I have expanded the first few terms such…
user588955
2
votes
3 answers

Consider the Fibonacci sequence $\{a_n\}$

Consider the Fibonacci sequence $\{a_{n}\}$ Use mathematical induction to prove that $a_{n+1}a_{n-1}=(a_{n})^{2}+(-1)^{n}$ So far, I have tested the base case $n=1$ which is true. I am stuck on the inductive step where I plug in…
John Doe
  • 41
1 2 3
…
99 100