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
1
vote
1 answer

Recurrence induction finding a constant $b$ such that $f(n) \leq bn$

Pretend induction is just a weird way our teacher uses induction when it comes to finding constant. Same as induction Base Case: let $n = 1$ $f(n) = 6(1) = 6$ and $bn = b$. Therefore we need $b \geq 6$ (*) let $n = 2$ $f(n) = 6(2) = 6$ and $bn =…
Tinler
  • 1,061
1
vote
2 answers

Find a formula for $\prod_{i=1}^{2n-1} \left(1-\frac{(-1)^i}{i}\right)$ then prove it.

Find a formula for $\prod_{i=1}^{2n-1} \left(1-\frac{(-1)^i}{i}\right)$ then prove it. I assumed that $\prod_{i=1}^{2n-1} \left(1-\frac{(-1)^i}{i}\right)=\frac{2n}{2n-1}$ after doing a few cases from above then I tried to prove it with induction…
HighSchool15
  • 2,061
  • 14
  • 35
1
vote
0 answers

Help find induction question

starts with the definitions of 2 sequences $D_1,D_2,D_3,\cdots \text{and } E_1,E_2,E_3,... . $ The rest of the question says: Use induction to prove that $E_n = D_n$ for all $n \geq 1$. Does anyone know where to find a similar question like this?
Tinler
  • 1,061
1
vote
1 answer

Recurrence induction show $f(n) = c4^{n} - d2^{n}, \forall n \in \mathbb N$

Use induction to find positive $c, d \in \mathbb R$ such that $f(n) = c4^{n} - d2^{n}, \forall n \in \mathbb N$ My attempt! Base Case: Let $(n = 0)$ $f(n) = 5$ [Def of f] and $c4^n - d2^n = c - d$ Therefore we need $5 = c - d$ (*) Inductive step:…
Tinler
  • 1,061
1
vote
2 answers

Induction for a Double Sided Inequality

For the question below I have split the inequalities into two and currently have LS $$\frac{1}{4} k^4 + k^3 < \frac{1}{4} (k+1)^4$$ RS $$\frac{1}{4} (k+1)^4 < \frac{1}{4} k^4 + (k+1)^3$$ I am unsure of what I am solving for after this. When one side…
user490305
  • 21
1
vote
2 answers

A few questions about a question involving mathematical induction

Suppose we have a sequence of numbers defined recursively as follows: $$ d_n = \begin{cases} 0 & \text{if } n=1; \\ 2d_{n-1}+2 & \text{if } n \geqslant 2. \end{cases} $$ Using mathematical induction, prove that for every integer $n\geqslant 1,…
bassie
  • 19
1
vote
3 answers

Induction - why do we allow $k=1$ in the second step?

Having proved that the property holds for the first case (most often 1), in the second step we need to assume that it's true for some $k \ge 1$. Why not $k>1$
Aemilius
  • 3,699
1
vote
3 answers

Why can we use mathematical induction to prove that $2^n \ge n^2$ for $ n \ge 5$

Why can we use mathematical induction to prove that $2^n \ge n^2$ for $ n \ge 5$ Normally, the proof via mathematical induction starts with $n =1$. Why does it still hold, when we start with other numbers?
Aemilius
  • 3,699
1
vote
3 answers

Mathematical induction for inequalities with a constant at the right side

Thanks to How to use mathematical induction with inequalities? I can now work with some induction problems related to inequalities. I've been following the logic that I was presented there so far. Until for $n\ge1$, I had to prove the…
Saturn
  • 7,191
1
vote
1 answer

Induction proving method for (n+1)! >= 2^n

I want to prove, using mathematical induction, the following proposition: $$ \forall n\in \:\mathbb{N}\:,\:\:\:\left(n+1\right)!\:\ge \:2^n $$ My thesis is this: $$ \forall n\in \:\mathbb{N}\:,\:\:\:\left(p+2\right)!\:\ge \:2^{p+1} $$ Thank you for…
Miguel Ferreira
  • 183
1
vote
0 answers

qq -induction step for $1+3+5+...+(2k-1)=k^2$

I'm trying to prove that $ 1+3+5+...+(2n−1)=n^2$ where $ n>= 1$ but I'm a little confused how my induction step should look like for $S(k)= 1+3+5+...+(2k-1) = k^2$ should it be $S(k+1) = 1+3+5+...+(2k-1)+((2k+1)-1) = (k+1)^2$ or…
Ward
  • 9
1
vote
2 answers

Finding the product $\prod_{k=2}^n \left(1 - \frac{1}{k}\right)$ using Induction

I'm trying to figure out how to prove by induction the following statement: $$ \prod_{k=2}^n \left(1 - \frac{1}{k}\right) = \frac{1}{n}. $$
Del
  • 11
1
vote
1 answer

Proving by induction that order of the product is equal to the product of the orders

I am trying to prove (by induction on k) that if $o(a_i) = n_i$ for all $i \in \mathbb{N}$ and $gcd(n_i,n_j)=1$ for all $i,j \in \mathbb{N}$ then $o(a_1a_2\dots a_k) = n_1n_2\dots n_k$. Where $o(n)$ denotes the order of the element $n$. My base…
meijiu
  • 87
1
vote
1 answer

recurrence induction

Consider the following recurrences allowing function $g_2:\mathbb N\to \mathbb N.$ $g_2(n)=\begin{cases} n+1 &\;\text{if $n=0$ or $n=1$}\\ n+1+\sum_{i=1}^{n-1} (i.g_2(n-1-i)) &\;\text{if $n>1$} \end{cases}$ $g_2(n) = 2^n$ for all $n\in\mathbb N$ is…
Tinler
  • 1,061
1
vote
4 answers

We can use an unlimited supply of 4-cent and 7-cent postage stamps to make (exactly) any amount of postage that is 18 cents or more.

$P(n)$: postage of exactly n cents can be made using only 4 cents and 7 cents Basis ($n=18$) $1 \cdot 4 + 2\cdot7 = 18$, thus $P(18)$ holds Induction step: Let $i$ be an arbitrary number such that $i \geq18$ and suppose that $k, L \in \mathbb N$…
jimmy jimmy
  • 27
1 2 3
…
99 100