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

Using induction to prove formula

I am revising for my test from Discrete math. I have come to this problem. I am to prove by using mathematical induction that $6\times7^{n} - 2 \times 3^{n}$ is divisible by 4. for $n \ge 1$ ; I created basic step : $6\times7^{1} - 2\times3^{1} =…
J.dd
  • 33
2
votes
2 answers

Proving $\frac1{2^n}<\frac1n$ inductively

I know this is probably a trivial proof but I'm struggling with it for some reason. The base case is trivial. I'm stuck at the inductive step where $$\frac1{2^{n+1}}<\frac1{n+1}$$ I'm completely stumped and I have no idea how to proceed.
Nikitau
  • 1,353
2
votes
3 answers

Cake Induction problem

A crowd of at least two people stands in a room and each one holds a cake. At the sound of a whistle, each person throws their cake at the person closest to them. (Before you ask: no one throws cake at himself.) If the number of people in the crowd…
JJMin
  • 21
2
votes
1 answer

How to prove this $\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$ with induction?

We have : $\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$ So first step, base of induction. If we take $n=1$ we get $1=1$. Assuming that his equality $\sum_{l=0}^{n}l\binom{n}{l}=n2^{n-1}$ is true, we need to prove…
Tars Nolan
  • 387
2
votes
5 answers

Proving that $1\cdot 2+2\cdot 3+\cdots+n\left( n+1 \right) =\frac { n\left( n+1 \right) \left( n+2 \right) }{ 3 } $ by induction

Prove that $$1\cdot 2+2\cdot 3+\cdots+n\left( n+1 \right) =\frac { n\left( n+1 \right) \left( n+2 \right) }{ 3 }. $$ I can get to $1/3(k+1)(k+2) + (k+1)(k+2)$ but then finishing off and rearranging the problem to $1/3(k+2)(k+3)$ is where I…
user2733843
  • 61
  • 1
  • 6
2
votes
4 answers

For all integers $n ≥ 2, n^3 > 2n + 1$

I am having some serious trouble figuring out this induction problem. I've tried following other problems and can not seem to get the end result or understand it sufficiently. My attempt: Theorem: For all integers $n≥2, n^3 > 2n + 1$ Proof: We will…
CaSrBa
  • 23
2
votes
4 answers

Induction Proof $2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{ 2}$

I am looking for an induction proof... $$2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{2}$$ when $n \geq 1$. I know there are $3$ steps to this. 1) Check 2) Do $n = k$ 3) Do $n = k + 1$ Problem is, I can't seem to get past the first step,…
Fenris
  • 37
2
votes
2 answers

Why can we assume a statement is true for $n = k$, when using induction?

I know the principle of mathematical induction. The only thing that causes my confusion is that we suppose a statement is true for $n=k$ then we prove the statement is also true for $n=k+1$ but how can we suppose $n=k$ to be true? What if a…
Waqar
  • 267
2
votes
2 answers

Use induction to show $\sum_{j=1}^x (4j - 1) = x(2x+1)$

Here is what we are given Use induction to show that for all $x$ $\in$ $\mathbb{Z}^+$ $$\sum_{j=1}^x (4j - 1) = x(2x+1)$$ This is what I have done Sometimes I find sigma notation a little confusing but here is my expansion of the question: $$(4*1 -…
Rubicon
  • 616
2
votes
1 answer

proof by simple mathematical induction question

"Prove using simple induction that for each integer $n \geq 1$, $$ 5 + 5^2 + 5^3 +..... + 5^n = \frac{5^{n+1}-5}4 $$ so I start with base step base step: $n = 1$ $$5^1 = \frac{5^{1+1}-5}4 $$ is correct. induction step: so we assume that $P(k)$ is…
discord1
  • 43
2
votes
2 answers

Induction proof that for every convex n-corner there are n(n-3)/2 diagonals

I have to proof that that for every convex n-corner there are $n(n-3)/2$ diagonals. 1.First step is to find n for which the sentence is correct. If $n0 = 3 => n(n-3)/2 = 0$. It is true because triangle has no diagonals. 2.Let's assume that…
FieryCod
  • 157
2
votes
1 answer

Prove Lucas numbers and Fibonacci numbers relation $F_n = \frac{L_{n - 1} + L_{n + 1}}{5}$

$F_n$, is the $n$th term of the Fibonacci sequence. $L_n$ is the $n$th Lucas number. I want to prove that $F_n = \dfrac{L_{n-1}+L_{n+1}}5 $. Things I know: $L_n$+$L_{n+1}=L_{n+2}$ $F_{n-1} + F_{n+1}=L_n$. The base case is easy to prove. I will…
hajeet
  • 21
2
votes
2 answers

Prove by induction that: $\sum^{2n}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^n_{i=1}\frac{1}{n+i}$

Basis step: For $n=1$, equation holds. Inductive step: Now, $$\sum^{2n}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^n_{i=1}\frac{1}{n+i} \tag{i. h.}$$ Now we want to show that $$\sum^{2n+2}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^{n+1}_{i=1}\frac{1}{n+1+i}.$$ So, $$…
Gjekaks
  • 1,133
2
votes
0 answers

Induction on Binary Trees

I am trying to show that $\sum_{i=1}^{M} 2^{-di} \leq 1 $ for a Binary Tree with $M$ leaves each with a depth of $d_i$. I understand intuitively why this is the case, as every subtree at level d, can at most contribute $2^{-di}$ to the above sum,…
Thalatta
  • 155
2
votes
1 answer

Continuum Induction

I have a question: Suppose we have a statement $P(x)$. If we show that: $\forall x \in (0,1]$, $P(x)$ is true. $P(x) \Rightarrow P(x+1)$ Then have we shown $P(x)$ holds $\forall x \in \mathbb{R}$, $x>0$? My reasoning here is…
M10687
  • 3,250
1 2 3
…
99 100