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

Proof by simple induction, question concerning the inductive step

Sorry in advance for posting a picture instead of the text, I'm not familiar with Latex yet... My question is... Why do we get: 4n^2 + 12n + 7 = 4((n − 1) + 1)^2 + 12((n − 1) + 1) + 7 And not this: 4n^2 + 12n + 7 = 4(n+1)^2 + 12(n+1) + 7 Proof
Norton
  • 21
  • 3
0
votes
1 answer

Is the following Strong Induction conclusion true?

can someone verify if this is true? I assume that P(i) holds for i < n, but then I would believe that this means the conclusion should be 3^n-1 and not 3^n. However, the correct answer given by my teacher says 3^n is correct.
Norton
  • 21
  • 3
0
votes
1 answer

How to show the number of domains the disk is split into is $1+ C_n^2 + C_n^4$?

Assuming there are n points on a circle, then there are $C_n^2$ chords. If any three chords don't intersect in circle. How to show the circle will be divided into $1+ C_n^2 + C_n^4$ domains? Picture below is a example of 5 points on circle.
Enhao Lan
  • 5,829
0
votes
0 answers

Example of inductive step working but not the base case

Are there any examples where the inductive step works but the base case does not? I know there are some where the latter is more difficult.
J. Dionisio
  • 437
  • 2
  • 14
0
votes
1 answer

Induction on a sequence inequality

Let a sequence $X_0, X_1, X_2, . . .$ be defined in the following way: \begin{equation*} X_0 = 1 \end{equation*} \begin{equation*} X_1 = 2 \end{equation*} \begin{equation*} X_n = 3X_{n−1} + 2X_{n−2}. \end{equation*} Prove that $\forall n \geq 0 :…
K. Zoe
  • 1
0
votes
2 answers

Mathematical Induction proof with triangular number sequence w/ alternating positive and negative #'s

Consider the following five equations: 1) 1 = 1 2) 1 – 4 = -(1 + 2) 3) 1 –4 + 9 = 1 + 2 + 3 4) 1 –4 + 9 –16 = -(1 + 2 + 3 + 4) 5) 1 –4 + 9 – 16 + 25 = 1 + 2 + 3 + 4 + 5 Conjecture the general formula suggested by these five equations, and prove…
Xandra Wolfbane
  • 3
0
votes
2 answers

Prove $x \geq 2$ implies $x^{n} \geq 2^{n}$

Prove $x \geq 2$ implies $x^{n} \geq 2^{n}$. By induction. Clearly it holds for $n = 1$ by the assumption. Now assume $x \geq 2$ and $x^{k} \geq 2^{k}$ for some $k \in \mathbb{N}$. Then combine the assumption inequality and $x \geq 2$ to get $x…
user592402
0
votes
1 answer

Mathematical Induction Prove the Formula

Given a positive number $a$ and a positive integer $k$. Let the sequence $x_n$ be given recurrently: $x_1 = a^{\frac{1}{k}}$, $x_{n + 1} = \frac{a}{x_n} ^ {\frac{1}{k}}$. Prove that the general term formula has the form $x_n = a^{\frac{1 - (- k) ^{-…
sclerd
  • 1
0
votes
2 answers

Prove by mathematical induction that $\sum_{i=0}^n (n-i)2^i = 2^{n+1}-n-2$

I'm trying to prove this by mathematical induction, but I just can't seem to get the answer that I should be getting. Here's what I have so far: Let $P(n)$ be the statement (this is the equation that I'm supposed to prove by induction):…
pythonprogrammer12
  • 3
0
votes
3 answers

Strong induction confusion

In strong induction i do not understand why lets say you proved the base case n=1 Then you assumed that the statement is true for all n from 1 to k, where k is some number in N. And in the induction step you need to use the truth of say k-2, so k-2…
hitherematey
  • 105
0
votes
3 answers

Induction definition

Suppose $T$ is a subset of $N$ Property 1: $0 \in T$, and Property 2: For every natural number $n \ge 1$, if $n − 1 \in T$ then $n \in T$ Hi this is how POI is introduced in my notes and then it is stated in the more common way. Im wondering if this…
Carlos Bacca
  • 638
0
votes
0 answers

Dn denotes the squares of a 2-by-n board using plain dominos. Then we see D1 = 1, D2= 2, and D3 = 3. find more values of Dn and guess an expression.

I understand this problem that this sequence is a Fibonacci sequence. Also, Fibonacci series is f(n) = f(n-1) + f(n-2). However, I am stuck on how to prove this using strong induction. I am at this step: Dk+1 = Dk + Dk-1. I do not where to go from…
learner
  • 1
0
votes
2 answers

How to present this inductive proof more clearly

Not sure where to go with this $2^k > k^3$ for $k > 9$ $2^(k+1) > (k+1)^3$ $2^(k+1) = 2^k \cdot 2$ $2^k \cdot 2 > k^3 \cdot 2$ (by inductive hypothesis) $2^k \cdot 2 > 2k^3$ $2k^3 > k^3 + 3k^2 + 3k + 1$ $2k^3 > (k+1)^3$ I know the final inequality…
user60862
  • 503
0
votes
0 answers

Prove by induction that $x^{r+s}=x^rx^s,x^{rs}=(x^r)^s,x^ry^r=(xy)^r\forall r,s\in \mathbb{Q}$ and $x,y\geq0$

I already have proved by induction that the equalities are true $\forall r,s\in\mathbb{Z}$ Because induction only works for statements that uses natural numbers. We first of all have to find a bijection from $\mathbb{Q}\rightarrow\mathbb{N}$ and…
RM777
  • 987
0
votes
2 answers

Mathematical Induction: For all n∈N and p∈R with p>=-1; 1+np<=(1+p)^n

For all n∈N and p∈R with p≥-1; 1+np≤$(1+p)^n$; prove by mathematical induction. So I know that you start with n=1, then assume P(k) is valid and then prove P(k+1). How do I prove that with the p≥-1. Do I need to prove for p+1 as well?
Karl Tesch
  • 11
1 2 3
…
99 100