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

How to solve $5x+9y=n$?

Show that $n_0 = 32$ is the smallest value of $n$ for which the equation $5x+9y=n$ has a solution in $(\mathbb N \cup \{0\})^2$ for all $n \geq n_0$. Wouldn't $(x,y)=(1,1)$ be a valid solution for $n=14$? The example that appears before this…
sant
  • 31
0
votes
1 answer

Prove $\sum_{k=0}^n (k + 1)\binom{n}{k}= 2^{n - 1}(n + 2)$

I am looking at the following problem and can not get any further. $$\sum_{k=0}^n (k + 1)\binom{n}{k}= 2^{n - 1}(n + 2)$$ Induction begin for $n = 0$ $$ \sum_{k = 0}^{0} (k + 1)\binom{0}{k} = 2^-1 (0 + 2) \\ 1 = 1 $$ Shows $n$ holds, then $n + 1$…
curiouscupcake
  • 231
0
votes
1 answer

Proof by strong induction for odd and even sequence

I have a proof by strong induction question (I won't ask the full question since someone in a previous course got in trouble for it). We basically have to prove, for a recurring sequence, that when $n$ is an odd the result of $S(n)$ is odd and when…
tom.rey04
  • 21
0
votes
2 answers

How to prove this inequality by using induction?

If $x,y$ are distinct real numbers such that $x+y>0$ and $n\ge 1$, then $2^{n-1}(x^n+y^n)\ge (x+y)^n$. It is obvious for $n=1$. How to do the rest by using induction?
user73564
  • 569
0
votes
0 answers

Prove by induction that $\sin\left(x\right)\ldots \sin\left(2^{n}x\right)=\frac{\sin\left(2^{n+1}x\right)}{2^{n+1}\sin\left(x\right)}$

Prove the identity by using the induction theorem: $$\sin\left(x\right)\sin\left(2x\right)\sin\left(4x\right)\ldots \sin\left(2^{n}x\right)=\frac{\sin\left(2^{n+1}x\right)}{2^{n+1}\sin\left(x\right)}$$. Basic Step:…
Diego Gallo
  • 161
0
votes
1 answer

Any hints for a proof by mathematical induction?

$$x^{\left(n-1\right)}+x^{\left(n-2\right)}c+x^{\left(n-3\right)}c^{2}+...+c^{\left(n-2\right)}+c^{\left(n-1\right)}=\frac{x^{n}-c^{n}}{x-c}$$ Where n is a positive integer So step one is to test when $n=1$. I cannot even do this step. The $RHS = 1$…
user71207
  • 1,543
0
votes
1 answer

Prove by induction $n^{n}>2^{n}\times n!$

Prove by induction $n^{n}>2^{n}\times n!$ for all $n\geq6$. This is what I've got at the moment. Still not sure whether is the right way to solve it by induction: Basic Step: Show that $S(1)$ is true for …
Diego Gallo
  • 161
0
votes
5 answers

Proving $\forall n \geq10, n^3 < 2^n$

Im asked to prove the following: $$\forall n \geq10, n^3 < 2^n$$ I'm 100% sure that the easiest way to prove this is via induction but I'm not being able to do so. How can I prove this?
Eduardo Magalhães
  • 4,878
0
votes
1 answer

Prove by induction $\ n^{\log_2(n)} \le e^n $

prove for any $\ n \ge 1 $ $\ n^{\log_2(n)} \le e^n $ Since both positive for every $\ n \ge 1 $ I was thinking of taking the $\ln $ of each function and then: $\ln(n^{\log_2(n)}) \le \ln(e^n) \Rightarrow \log+2(n) \cdot \ln(n) \le n$ and for $\ n =…
bm1125
  • 1,427
0
votes
1 answer

prove that $(k+1)^a - 1$ is divisible by k

prove that $(k+1)^a - 1$ is divisible by k Base case: n = 0; $(k+1)^0$ -1 = k which is divisible by k IH: $(b+1)^a - 1$ is divisible by b for a + 1 $(b+1)^{a+1}$ -1 = $(b+1)(b+1)^{a} -1 $
hjkl
  • 5
0
votes
1 answer

A generalized version of a classic induction proof

It's a very classic problem for students learning induction to prove the following statement: "Prove $n! > 2^n$ for all $n \geq 4$" I went on to prove a related, still quite simple example: "Prove $n! > n^2 2^n$ for all $n \geq 8$." This isn't very…
user817934
0
votes
1 answer

Understanding What Parts of a Mathematical Induction Problem Means

So I am trying to prove by induction that $3$ divides $n^3+2n$ whenever $n$ is positive. So far I have: $$\text{Assuming $P(n)$ is true, we'll prove $P(n+1)$ is also true.} \\ (n+1)^3 +2(n+1)\\ n^3+3n^2+3n+1+2n+2…
user750949
0
votes
1 answer

Mathematical induction proof for $A_n = [-1 + \frac{1}{2n}, 1-\frac{1}{n}]$, $\bigcup\limits_{n=1}^{+\infty} A_n$ = $]-1, 1[$

$ \forall \in \mathbb{N} $, let $A_n = [-1 + \frac{1}{2n}, 1-\frac{1}{n}]$, find $\bigcup\limits_{n=1}^{+\infty} A_n$. I know (hypothesize) that the answer is tending towards $$]-1,1[$$ and that $$A_n \cup A_{n+1} = A_{n+1}$$ hence…
Heng Wei
  • 303
0
votes
1 answer

Proof by induction that $\sum_{i=1}^n i/2^i=2-(n+2)/2^n$

Prove by induction that $$\sum_{i=1}^n \frac{i}{2^i}=2-\frac{n+2}{2^n}.$$ this is a question that must be proved by induction. For the base case I used $n=1$ and simplified to $1/2$ and now for the inductive step $$p(k)\to…
user803476
0
votes
1 answer

Proving inequality question using mathematical induction

I'm having a really hard time on how to prove this using mathematical induction: For all real $x>-1$, $(1+x)^n\geq 1+nx$. Edit: (Solution with the help of comments and answer below) If $x>-1$ then $1+x>0$ Base case $n=1$: $(1+x)^1\ge 1+x$.…
Luís Fernando
  • 5
1 2 3
…
99 100