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

Prove by strong induction a "recursive algorithm" form of the 5th Peano axiom

The given recursive algorithm is as follows: If an algorithm $P$ has one argument $n$ of type natural, it terminates when called with the argument $0$. When called with an argument $x > 0$, it terminates, except possibly for a call to itself with…
user2898453
  • 1
0
votes
1 answer

Induction proof of $a^r \ge 1$

I understand induction with one variable well, however I am not sure what to do when there are 2 or more variables. The problem I came across is following: Prove that $a^r \ge 1$, where $r \in \mathbb{N}$ and $a \in \mathbb{R} \wedge a \ge 1$ My…
John Smith
  • 17
0
votes
2 answers

Proving $k^2 > 2k + 1$

Question: Prove $2^n > n^2$ for $n > 4$ Going to fast forward to my problem so: Base case: $n = 5$ true Induction step: Suppose true for $n = k > 4$ true, i.e. $2^k > k^2$. Now consider $n = k+1$: $$\begin{align} 2^{k+1} &= 2(2^k) \\ &> 2(k^2)…
Aean
  • 113
0
votes
3 answers

Show $\sin (x + 180n)$ = $sin \cdot (-1)^n$ for integers n > 0

I have two questions: 1) When we assume $n = k$ true, what is the restriction on integer k? I have been told k does not include the first case of n we tested for i.e. k > 1 which makes sense as n = k is an ASSUMPTION and n = 1 is already true. 2)…
Aean
  • 113
0
votes
2 answers

Given an induction definition, how to calculate elements?

I'm having difficulty with a mathematical problem. I've got the following; The basis is: -1 ∈ V And the induction is; x ∈ V → x/(1-x) ∈ V Now, I have made 4 statements and I want to get to know if they're either true, or false. The statements…
MichaelP
  • 45
0
votes
3 answers

Mathematical induction proof I'm stuck on

Use mathematical induction to show that $3^{3n} + 2^{n+2}$ is divisible by 5. Any help would be appreciated thanks!
user95126
  • 21
0
votes
1 answer

Let f be a positive integer be define recursively by $f(1)=1$ and $f(n+1)=\sqrt{2+f(n)}$ for all integers n. Prove that $f(n) = (2^n)-1$.

Let f: be a positive integer defined recursively by $f(1)=1$ and $f(n+1)=\sqrt{2+f(n)}$ for all integers n. Prove that $f(n)<2$. I am supposed to prove this by using proof of induction. I've tested the base case of 1, and I've let $P(n)$ be the…
user97663
  • 1
0
votes
2 answers

proof by mathematical induction divide a convex polygon of n sides into triangles

The question is "Determine the number of diagonals (that do not intersect) necessary to divide a convex polygon of n sides into triangles." I am having problems approaching this question can any one give me some ideas of how approaching these types…
Ahmed.yu
  • 17
0
votes
1 answer

Induction question

I have this homework question in Proofs by Mathematical Induction and I don't have a clue how to resolve it, is there anyone that can help me? When you roll a die you have $6$ possible outcomes $1,2,\ldots,6$. When you roll two dice you have $11$…
Dröfn
  • 3
0
votes
2 answers

The derivative of $f(x)=\sin(ax+b)$

Use mathematical induction to prove that the derivative of $f(x)=\sin(ax+b)$ is given by $f^{(n)}(x)= (-1)^ka^n\sin(ax+b)$ if $n=2k$, and $(-1)^ka^n\cos(ax+b)$ if $n=2k+1$ for a number $k=0,1,2,3,...$ I have done som proofs by induction, but I seem…
user71671
  • 81
0
votes
2 answers

Induction proof $n^2 < 2^n$ for $n > 4$

I need to prove that $n^2 < 2^n$ for all natural numbers $n$ greater than $4$. I understand that you start by proving the base case of $n = 5$ and then prove the inequality substituting the inductive hypothesis for $n + 1$, but I am unsure about how…
user95420
  • 25
0
votes
1 answer

What is wrong with my induction proof?

I have been stuck on this proof for over an hour and just cannot wrap my head around what I am doing wrong. I have to proof the following: $$P_n:\sum_{i=1}^n\frac i{3^i}= \frac34-\frac {2n+3}{4\cdot3^n} \quad (n \in \mathbb{N})$$ My proof: $$P_0:\;…
CaptSellerie
  • 9
0
votes
2 answers

Prove by induction that $2^n > n^2+ 4 n + 5$ $\forall n \ge 7$

I have seen the solution to this problem where for the induction step we have: $$2^{n+1} = 2 \cdot 2^n \gt 2 (n^2 + 4 n + 5) = (n + 1)^2 + 4(n + 1) + 5 + n^2 + 2 n \gt (n + 1)^2 + 4(n + 1) + 5$$ In this induction step we prove the inequality from…
Jordi
  • 687
0
votes
0 answers

Proof by induction $uf(n)+f(n-1)=g(n)\equiv 0\pmod x \implies f(n)\equiv 0\pmod x$

I am trying to prove the following proposition by induction. I got stuck . Please help. $$uf(n)+f(n-1)=g(n)\equiv 0\pmod x$$ where $u\in\mathbb Z_{\ge 0}$, and $n\in\{1,2,\cdots,p-2\}$. If $f(0)\equiv 0\pmod x$ and $g(0)\equiv 0\pmod x$…
NumThcurious
  • 325
0
votes
3 answers

If a statement is true for a particular n and for n+2, what needs to be done to prove the statement is true for every positive integer?

I am a bit confused with this question and any clarification or suggestions would be greatly appreciated. Suppose that there is a statement involving a positive integer parameter n and you have an argument that shows that whenever the statement is…
Suzanne Frank
  • 357
1 2 3
…
99 100