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

Question regarding proving by induction

I am struggling with a math problem I have been assigned. The problem is as follows: Let $X_1 = -3$ and $X_2 = 0$. Given that for every natural number $n \geq 2, X_{n+1} = 7X_n - 10X_{n-1}$, prove by induction that for every $n$ belonging to…
Biggytiny
  • 127
1
vote
2 answers

Proving $n^2≤2^n+1$ for $n\geq 1$ by induction

Prove $n^2\leq 2^n+1$ for $n\geq 1$ using induction. Proof. For $n=1, (1)^2\leq 2^1+1=3$. $\therefore 1\leq 3$ is true. Assume $n=k$ is true so $k^2\leq 2^k+1$ or $k^2-1\leq 2^k$. Then prove for $n=k+1$. Goal: $(k+1)^2\leq 2^{k+1}+1$ We…
Natasha Epperson
  • 93
1
vote
2 answers

Help with solving mathematical induction problem

I need help with the following: Use mathematical induction to prove that for every $n\in N$, $$ \sum_{k=1}^n\frac{1}{\cos kx \cos(k+1)x}=\frac{\tan(n+1)x-\tan x}{\sin x} $$ For $n=1$, the statement is true. Suppose that the statement is true for…
user300045
  • 3,449
1
vote
3 answers

Simple Induction Proof

How would one go about proving that $$0<\frac{n}{n+1}<1$$ by mathematical induction? If $p(n)$ is the statement as above, then I know we show $p(1)$, and assume $p(n)$, but in this particular case I am not sure know to show $p(n+1)$.
user138999
  • 410
1
vote
1 answer

Nim Variant - Strong Induction Proof

Here we will play a variant of Nim where there is an additional move option in some cases. If two or more piles have the same number of stones, a player may remove the same number of stones from both of them. For example, if the contents of the…
j226
  • 35
1
vote
4 answers

Prove by strong induction that $2^n$ divides $p_n$ for all integers n ≥ 1

Let $p_1 = 4$, $p_2 = 8$, and $p_n = 6p_{n−1} − 4p_{n−2}$ for each integer $n ≥ 3$. Prove by strong induction that $2^n$ divides $p_n$ for all integers $n ≥ 1$ I got up to the base step where by you prove for $p_3$ but unsure about the strong…
dave
  • 103
1
vote
2 answers

Proving by strong induction for a sequence of integers, $2^n$ divides term $n$

Provided the following sequence of integers $t_1, t_2, t_3$,... is defined as: $t_1 =4, t_2 =8$ and $t_n= $ $ 6t_n$$_-$$_1$ - $4t_n$$_-$$_2$ for all integers $n \geq 3$ How do we prove that $2^n$ divides $t_n$ for all integers $n \geq 1$ by…
user230428
1
vote
1 answer

Help with the Inductive step in mathematical Induction?

I just started working on Induction, and I have one particular problem that I don't understand: Prove that $1+3+5+...+(2n−1)=n^2$ for any integer $n≥1.$ $n = 1$ : $1 = 1^2$ $n = k$ : $1+3+5+...+(2k−1)=k^2$ $n = k+1$ : (this is where I have a…
user3170251
  • 213
1
vote
2 answers

Proof that a recursively defined sequence is monotonically decreasing.

I am wanting to prove that the following recursive sequence is monotonic decreasing via proof by induction. Let $ S_1 = 1, ~ S_{n+1} = \frac{n}{n+1} (S_n)^2;~ n \geq 1. $ Here is what I have so far but I feel the proof fails at my last statement…
sho
  • 205
1
vote
1 answer

Is Proof By Induction Necessary?

Are there any theorems that can only be proved by induction? Induction seems to be proof by technicality.
Jimmy360
  • 649
1
vote
1 answer

Induction Proof: Inequality involving Summation of Products with Squared Terms

I was trying to solve one of the bounty questions (yes i know it is very ambitious for a newbie like me:-) ). But regardless of my analysis being correct or incorrect, another problem originated from my answer which required proving or disproving…
Comic Book Guy
  • 5,748
1
vote
1 answer

Show by induction: $ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}$

I would appreciate if somebody could help me with the following problem: Q: Sequence $\{a_n\}$; satisfy $a_{n+2}=a_{n+1}+a_{n}, a_1=1,a_2=1$ Show by induction: $$ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}$$ I tried…
Young
  • 5,492
1
vote
2 answers

Proof by exhaustion:

We are given that a polynomial f(x) has integer coefficients. The coefficient of x^4 being 1. One root of it is ($\sqrt{2}+\sqrt3$). How do we find the other roots? I tried using long division, it was so long so i just did it until $x^2$, like I…
Arbi
  • 23
1
vote
2 answers

Proof $\frac{a_n^2+a_{n+1}^2+1}{a_{n}a_{n+1}} $ is constant

I would appreciate if somebody could help me with the following problem: Question: Defined by $a_{1} =1,a_{2}=2$ and $a_n a_{n+2}=a_{n+1}^2+1(n\geq 1)$ Proof. $\frac{a_n^2+a_{n+1}^2+1}{a_{n}a_{n+1}} $ is constant for $n\geq 1$ I tried…
Young
  • 5,492
1
vote
2 answers

Reverse inductive proof

This is probably a stupid question. Let us say I were to prove something by induction. Is it true, that the basecase must be the lowest possible number? If I wanted to prove that the formula holds for 1, 2, 3, ... , 999 for example, the basecase…
Arcthor
  • 91
1 2 3
…
99 100