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

Show, with induction that $1^2 + 2^2 + .... + n^2 = \frac{n(n+1)(2n+1)}{6}$

Show, with induction that $1^2 + 2^2 + .... + n^2 = \frac{n(n+1)(2n+1)}{6}$ My attempt Case 1: n = 1 $LHS = 1^2$ $RHS = \frac{(1+1)(2+1)}{6} = \frac{2*3}{6} = 1$ Case 2: n = p $LHS_{p} = 1^2 + 2^2 + ... + p^2$ $RHS_{p} =…
Daniel Andersson
  • 375
  • 2
  • 9
0
votes
1 answer

Prove that [n / 3] = O (n)

How should I start by proving this? I know that for very large N values ​​the difference between the two numbers will be minimal, but I do not know how to prove it to my concrete math teacher.
Leonardo Furtado
  • 1
0
votes
2 answers

Induction on a list of integers?

let $(a_1,\cdots,a_n)$ be a list of integers prove that if $a_1$ is even and $a_n$ is odd then there is an index $i$, $1\leq i < n$ such that $a_i$ is even and $a_i+1$ is odd. I’m extremely confused on how to even preform induction on this. What…
Dani Jo
  • 93
0
votes
3 answers

induction method for sqrt

$$(1+\sqrt 2)^n-(1-\sqrt2)^n=b_n\sqrt2$$ $$n\in N $$ $$b_n\in N$$ I needed to solve this by the induction method. The base and thesis of induction is easy, is to substitute n for n + 1, but I can not reduce the expression, someone could give an aid
Monica
  • 81
0
votes
1 answer

Proof with induction

Let $n\in\mathbb{N}$ and $x_1,x_2,x_3.....,x_n \in\mathbb{Q}$ with $x_i > 0$ and $\prod_{i=1}^{n} x_i = 1$ prove that $\sum_{i=1}^{n}x_i \geq n$ (hint:use induction). Been stuck on that for hours. It seems as if the terminology of the question is…
eran-avrahami
  • 91
0
votes
2 answers

Ordinary Induction

Define a function $f:\mathbb{Z}\to\mathbb{Z}$ by $f(x)=2x^2-8x+1$. Use ordinary induction to prove that $f(x)\geq 0$ for all integers $x\geq 4$. A bit perplexed on the IS. We solve for P(K+1) right? Can someone help me prove this?
Robin
  • 169
0
votes
0 answers

mathematical induction methods II

I still do not have the answers I want for this thread I made mathematical induction methods, or rather it made me more confused in what I potentially am doing wrong. So I will try to ask again and see what is wrong with the method (I do know how to…
Aurora Borealis
  • 1,747
0
votes
5 answers

Prove via induction $5^0 + 5^1 + 5^2 + \dots 5^n = \frac{5^{n+1}-1}{4}$

Statement: $$5^0 + 5^1 + 5^2 + \dots 5^n = \frac{5^{n+1}-1}{4}$$ I am having trouble prooving P(k+1) is true. Here is what I have so far: $$\frac{5^{k+1} -1}{4} + 5^{k+1} = \frac{5^{k+2} -1}{4} $$ LHS $$ \textrm{ stuck here} = \frac{5^{k+1}}{4} -…
Evan Kim
  • 2,399
0
votes
2 answers

Proving by induction $P_n \le 5 - \frac5n$

for $n\ge1$ let:$$P_n = (\frac21).(\frac54).(\frac{10}9).(\frac{17}{16})...(\frac{n^2+1}{n^2}) = \prod^n_{k=1}(\frac{k^2+1}{k^2}). $$ Prove by induction for $n\ge 2$: $$P_n \le 5 -\frac5n $$ I did ask a variation of this question before, the…
user60334
  • 717
0
votes
1 answer

Prove that, for every natural number $n$, $10^n > n^2$

I attempted to solve the proof but looking at another proof but I got stuck. Here's what I have so far. Let $n = 1$, $10 > 1$. Assume valid for $k$ greater than or equal to $1$. Then $n = k + 1$. $10^k > k^2$ .... Case(1) = $100 > 10$ And then…
Mark Park
  • 1
0
votes
0 answers

Prove the formula using "complete induction"

Let $S _ { n } = 2 \cdot S _ { n - 1 } + S _ { n - 2 }$ with $S _ { 1 } = 3$ and $S _ { 2 } = 7$. Prove that for every integer $n \geq 1$ $$S _ { n } = \frac { 1 } { 2 } ( 1 + \sqrt { 2 } ) ^ { n + 1 } + \frac { 1 } { 2 } ( 1 - \sqrt { 2 } ) ^ {…
Tariro Manyika
  • 111
0
votes
0 answers

Prove that $a_1.a_2......a_p<=((a_1+a_2+.........+a_p)/p)^p$, where $p=2^m$, using mathematical induction on m.

The quantities $a_i$ are all positive real numbers. (a) Show that $$a_1.a_2 \leq \left(\frac{a_1 + a_2}{2}\right)^2$$ (b) Hence prove, by induction on m, that $$a_1.a_2.......a_p \leq \left(\frac{a_1+a_2+......+a_p}{p}\right)^p$$ , where $p = 2^m$…
ujjwal
  • 1
0
votes
2 answers

Proof by Induction for $n^2\leq2^n$ .

I was given the following as part of a course on Abstract Mathematics that I am currently busy with. It is from a Book "An Introduction to Mathematical Reasoning" by Eccles. For all integers $n$ such that $n\geq4$, we have the inequality…
alortimor
  • 171
  • 7
0
votes
1 answer

Proof question that could be proved using mathematical induction.

$T_1=x+1/x$ is an integer greater than $2$. Prove that $x^n+x^{-n}$ is an integer. For what values on $n$, $t_1$ divides $t_n$. I am stuck with this problem. Please help.
Super MaxLv4
  • 45
0
votes
1 answer

Induction with two unknown variables

I have been at this problem for a while now, and I cannot wrap my head around it. Any kind of help would be greatly appreciated! The runtime for a sorting algorithm can be described by $a_{1} = 3$ and I need to prove, that For all $n, k \in…
jubibanna
  • 153
  • 5
1 2 3
…
99 100