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
2 answers

Prove by induction that $u_n=3\times2^{n-1}-1$ for all $n\ge1$

The sequence $u_1$, $u_2$, $u_3$,... is defined by $$u_1=2\,,\,\,\,\,\,\,\,\,\,u_{k+1}=2u_k+1$$ Prove by induction that, for all $n\ge1$, $$u_n=3\times2^{n-1}-1$$ You first have to prove that $u_1=2$ $$u_1=3\times2^{1-1}-1=3\times1-1=2$$ Then if I…
Thomas Winkworth
  • 641
2
votes
3 answers

How to prove through induction

How can I prove by induction that $$\binom{2n}n<4^n\;?$$ I have solved for the base case, $n=1$, and have formulated the induction hypothesis. I was thinking about Pascal's identity for the rest, but have not been able to come up with a way to use…
db2791
  • 197
2
votes
5 answers

Fibonacci sequence and the Principle of Mathematical Induction

Consider the Fibonacci sequence, $F_n$. Prove that $2 ~\vert~ F_n$ if and only if $3 ~\vert~ n$, using the principle of mathematical induction. I know that I have to prove two implications here. Looking at the first implication (if $2 ~\vert~ F_n$,…
Linda Kallash
  • 155
2
votes
1 answer

Prove or disprove $n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n} $$ And i am not clear whether it should be proved or disproved. my…
user117911
  • 89
2
votes
1 answer

n number of cans on a circular track will traverse a car around it

The 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.…
Zack Zatkin-Gold
  • 123
2
votes
2 answers

Is this statement of Mathematical Induction correct?

Theorem: Principle of Mathematical Induction For each natural number $n$, let $P(n)$ be a statement. If $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for every $k \geq 2$ Then $P(n)$ is true for all $n$. Shouldn't that be $k\geq1$? Otherwise, I…
Jonathan Hebert
  • 5,272
2
votes
2 answers

How is $(n+1)(n+2) / 2$ derived in this induction step?

I'm attempting to understand in how to get from step1 to step2 : Step 1. $1+2+\cdots+n = n(n+1)/2 $ Step 2. Need to show $1+2+\cdots+(n+1)= (n+1)(n+2) / 2$ How is $(n+1)(n+2) / 2$ derived from replacing $n$ in step 1 with $(n+1)$ ?
blue-sky
  • 2,100
2
votes
2 answers

Induction Proof with Factorials

Problem: If $0 \leq j \leq n-1$, then $(j+1)!(n-j)!\leq n!$. The hint is to use induction and a symmetry argument. Attempt: Base step for induction ($j=0$): $(0+1)!(n-0)! = n! \leq n!$ Induction step: Suppose the induction hypothesis holds for $j <…
Rocco
  • 23
2
votes
2 answers

Proof by induction $n^2-2n-1>0$ for $n \ge 3$

I want to use induction to prove that $n^2-2n-1>0$ for $n \ge 3$ Base case: $3^2-2(3)-1>0$ $ \space \checkmark$ Inductive step: $(n+1)^2-2(n+1)-1>0$ $\iff n^2+2n+1-2n-2-1>0$ $\iff n^2-2>0 \iff n^2>2$ Is it now trivial to just say that this…
qmd
  • 4,275
2
votes
3 answers

Induction proof, greater than

Prove that: $n!>2^n$ for $n \ge 4$. So in my class we are learning about induction, and the difference between "weak" induction and "strong" induction (however I don't really understand how strong induction is different/how it works. Here's my…
Math Major
  • 2,234
2
votes
3 answers

Proving with induction $(1-x)^n<\frac 1 {1+nx}$

Prove using induction that $\forall n\in\mathbb N, \forall x\in \mathbb R: 0
shinzou
  • 3,981
2
votes
2 answers

Proving that there are infinitely many Pythagorean quadruples by induction using described method

I want to prove that there are infinitely many Pythagorean quadruples by induction, using the following pattern: $1^2+2^2+2^2=3^2$ So I take $d=3$ and I want to prove by induction that I can form another quadruple with $d_1=d^2$. The hypothesis…
Lazar Ljubenović
  • 2,896
2
votes
0 answers

Prove by induction that 3 divides $n^3+2n$

Possible Duplicate: Proof that $n^3+2n$ is divisible by 3 How can I prove by induction that for any positive integer $n$, $(n^3 +2n)$ is divisible by $3$?
adil
  • 507
  • 1
  • 4
  • 4
2
votes
4 answers

Prove by induction (formula for $\sum^n(3i-1)^2$)

Anyone knows how to do this? The answer I'm getting is not correct. Prove by induction that, for all integers $n\ge1$, $$\sum_{i=1}^n (3i-1)^2 = \frac12 n(6n^2 + 3n - 1). $$ Thanks This Is what I have managed to get. After this I think I'm doing…
AkshaiShah
  • 585
  • 2
  • 7
  • 15
2
votes
1 answer

Proving by induction $3^{n-2}\le(n-1)! : \forall n\ge 6$

Prove by induction: $3^{n-2}\le(n-1)! : \forall n\ge 6$ The base case and hypothesis are trivial, we want to show that: $3^{n-1}\le(n)! : \forall n\ge 6$, but I get stuck very early: $3^{n-1}\le \frac{3\cdot3^{n-1}}{3}\overset{I.H}{\le}3(n-1)!\le…
shinzou
  • 3,981
1 2 3
…
99 100