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

Problem by proving a statement by induction

I want to prove the following statement by induction for $n\leq 1$: \begin{align*} \sum_{k=n}^{2n-1}\frac{1}{k}= \sum_{k=1}^{2n-1}\frac{(-1)^{k+1}}{k} \end{align*} For $n=1$ its easy to see: \begin{align*} \sum_{k=1}^{2-1}\frac{1}{k}=…
putti.123
  • 339
1
vote
2 answers

Mathematical Induction Check, $n! \leq n^n/2^n $

Hello I am working on this problem and was wondering if I did the proof correct. Use induction to prove that $n! \leq n^n/2^n $ for all $n \geq 6$. Basic Step (n=6): 6! $\leq 6^6/2^3 = 3^6$ Thus $80 \leq 81$, so the Basic Step is true. Assume the…
Username Unknown
  • 4,633
1
vote
1 answer

Prove by mathematical induction: $x^n - y^n$ is divisible by $x - y$, for all positive integers $n$.

Here is what I have so far: Base: When $n=1$, we have $x^1 - y^1 = x - y$. Hence, P(1) is true. Inductive hypothesis: We assume that P(k) is true: $x^k - y^k$ is divisible by $x - y$. That is: $x^k-y^k=(x - y)z$, for some integer $z$ Inductive…
Andy
  • 47
1
vote
3 answers

Infinite subset of $\mathbb{N}$ is countable. Proof by math induction.

Proposition: Infinite subset of $\mathbb{N}$ is countable. Proof: Suppose that $E$ is infinite subset of $\mathbb{N}$ and our goal to show that $E$ is countable, i.e. there is $f:\mathbb{N}\to E$ which is bijection. Since $E\neq \varnothing$ then…
RFZ
  • 16,814
1
vote
2 answers

determining the value of e by using mathematical induction

using the fact that $n!>2^{n}$ $\forall n\ge 4$ conclude that $e<\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\displaystyle\sum_{n=4}^{\infty}\frac{1}{2^{n}}$ where $e:=\displaystyle\sum_{n=0}^{\infty}\frac{1}{n!}=1+\frac{1}{1!}+....$ should I inverse the…
H.E
  • 2,056
1
vote
1 answer

Induction Proof Help

Q: By induction on n prove that for all positive integers $n^2\ge1$ A: When n=1, $$n^2\ge1=1^2\ge1$$$$1\ge1$$ Suppose n=k, $$n^2\ge1=k^2\ge1$$ ** This is as far as I can get unto without getting stuck, I know that I have to assume that n=k+1 for the…
MathStudent1999
  • 13
1
vote
0 answers

Proof by induction on generalized coin problem

The following statements can be easily proved by induction: If I have coins of $3$ and $5$ cents (then difference, $d=5-3=2)$, then I can pay any bill starting from $(3-1)(3+d-1)=8$ cents. If I have coins of $5$ and $9$ cents (then $d=4)$, then I…
Terrarium
  • 145
  • 5
1
vote
2 answers

Prove $1^3 + 2^3 + \ldots n^3 = \frac{n^2(n + 1)^2}{4}$ with mathematical induction

Hello guys I'm trying to prove this equation with mathematical induction method. So for n = 1 I know that : 1 = 1 Now I know that it works for some k I wanna prove it for k + 1: Since : I can rewrite it as : So I'm stuck here.. I…
Minotaur666
  • 57
1
vote
1 answer

Proof summary by induction

The question is : " proof for any N that -" $$\sum _{k=1}^n\:\left(-1\right)^{k+1}\cdot \left(2k-1\right)=\left(-1\right)^{n+1}\cdot n$$ I`ve reached to $$\left(-1\right)^{n+1}\cdot n+\left(-1\right)^{n+2}\cdot…
Tal Ouzan
  • 25
1
vote
0 answers

Turning a weak induction proof into a strong induction proof

In my proofs class, we're talking about strong induction and weak induction, and I don't really understand the difference. I get that for weak induction, we assume that an arbitrary $n = k$ is true, and then we set out to show that $n = k + 1$ is…
Crimson
  • 31
1
vote
1 answer

proving summation using induction

we need to prove that for ever $n∈N$ the following equality is right $$\frac{3\sum_{i=1}^n i^5}{{\sum_{i=1}^n i^3}} = 2n^2+2n-1$$ so first of i checked for n=1 and we get $$\frac{3\sum_{i=1}^1 i^5}{{\sum_{i=1}^1 i^3}} = 2*1^2+2*1-1$$ which is…
Adamrk
  • 909
1
vote
3 answers

proof with induction $2^n + 4 > n^2 + 2n$

prove w/ full induction : $2^n + 4 > n^2 + 2n$. Let's skip the other steps for a moment, I'm just getting stuck with the proof the claim is: $2^{n+1} + 4 > (n+1)^2 + 2(n+1)$ and now the proof $$2^{n+1} + 4 > 2 * 2^n + 4$$ $$> 2 * (n^2 + 2n)$$ $$>…
mathslooser
  • 45
1
vote
1 answer

Product Series Formula through Induction

For the series: $(1+\frac{1}{1})^1$$(1+\frac{1}{2})^2$$.....$ $(1+\frac{1}{n})^n$ I have the formula $\frac{(n+1)^n}{n!}$ for n$\in$ $\Bbb N$ I used induction to try and solve but I'm stuck at trying to prove it for n+1…
Wolf
  • 115
1
vote
3 answers

Prove by induction $\left(1-\frac{1}{2}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$

Prove by induction $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{4}\right)\left(1-\frac{1}{8}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$ What would be the best way to solve this by the induction method?
Diego Gallo
  • 161
1
vote
4 answers

prove $\ e^{n^2} \ge n^n $ for every n by induction

Prove for any $\ n \ge 1 $ $$\ e^{n^2} \ge n^n $$ my attempt: true for $\ n = 1 $ then for $\ n+ 1 $ : $\ e^{(n+1)^2} = e^{n^2 + 2n + 1} = e^{n^2} \cdot e^{2n} \cdot e $ $\ ( n+1)^{n+1} = (n+1)^n\cdot (n+1) \le (n+n)^n\cdot(n+1) = (2n)^n \cdot(n+1)…
bm1125
  • 1,427
1 2 3
…
99 100