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

Mathematical induction on Hanoi tower from book Concrete Mathematics

From the book "Concrete mathematics", I tried to solve the following warmup exercise: Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B, if direct moves between A and B are disallowed.…
Eduardo
  • 127
0
votes
1 answer

Problem solving an induction problem

Show that for every $n\ge1$ and for every real number $x\ne 1$ $\dfrac {x^{n+1}-1}{x-1}=1+x+x^2+\cdots +x^n$ is valid. By induction, put $n=1$ $x=2$ and you get for the base case: $$\frac{x^2-1}{x-1}=x+1$$ $$x+1=x+1$$ Then consider $n=m$ $\dfrac…
Luthier415Hz
  • 2,739
  • 6
  • 22
0
votes
1 answer

prove by induction Fibonacci sequence: $\forall n \geq 1, F_n \varphi+F_{n-1}=\varphi^n: \varphi \equiv \frac{1+\sqrt{5}}{2}$ ,conclude $\varphi^{10}$

I have this Fibonacci sequence $F_i=i, i \in\{0,1\}, F_n=F_{n-1}+F_{n-2}, n \geq 2$ and have to prove by induction that: $\forall n \geq 1, F_n \varphi+F_{n-1}=\varphi^n: \varphi \equiv \frac{1+\sqrt{5}}{2}$ and conclude $\varphi^{10}$ I've started…
engnajjar
  • 65
0
votes
1 answer

Doubt proving that there is no natural number between $n$ and $n+1$?

I'm trying to understand the solution to the following problem I took from Hijab's "Introduction to Calculus and Analysis": The solution is: We are using the following definition and theorem: And when he says "from the text" is that he…
Red Banana
  • 23,956
  • 20
  • 91
  • 192
0
votes
0 answers

Can someone please elaborate the statement given below?

"The above principle works because of the fact that every non empty set of positive integers has the least element. In fact it can be proved that the principle of mathematical induction is equivalent to the fact that every non empty set of positive…
Lakshya Kumar Singh
  • 11
0
votes
2 answers

Prove by Induction $19^{n}-4^{2n}$ is divisible by 3

Assume $n=0$ for $19^{n}-4^{2n}$ Just going to do some simplification first: $19^{n}-4^{2n}\implies19^{n}-16^{n}$ and if $n=0$ then $19^{0}-16^{0}$ then it is zero which is obviously divisible by 3. Now for the inductive hypothesis…
lifeiscool
  • 183
0
votes
1 answer

What affects the number of base cases that I need to prove when using strong induction?

Below are two particular problems to illustrate the question in the title. Problem 1 Given a sequence $\large a_1=1, a_2=2, ..., a_n= a_{n-1}+a_{n-2}$ prove that for all $n\in Z^+$, $a_n\le\bigg(\dfrac 7 4\bigg)^n$. My solution. With $n=1$ and $n=2$…
Elena
  • 117
0
votes
1 answer

Moment of normal distribution (Iproof by induction)

I want to show $$E(Z^{2k})=\frac{(2k)!}{2^kk!} \text{ for } Z\sim N(0,1).$$ I showed $$E(Z^{2k})=(2k-1)\cdot E(Z^{2k-2})$$ and guessed by trying (since $E(Z^2)=1$): $$E(Z^{2k})=(2k-1)!!$$ How do I prove this by induction? $k=1$ is true:…
Uhmm
  • 317
0
votes
2 answers

Breaking the implication chain in inductive reasoning

This is a question from An Invitation to Combinatorics. The question is as follow: A specific statement about the positive integer n is denoted by P(n). We can prove that, whenever P(k) is true, then P(k + 1) is also true. It is also known that…
Parth Patel
  • 3
0
votes
2 answers

Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$

Let $p,q\in\mathbb N$. Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$. Things I already proved and might help: $p^2\neq2$ if $(\frac{p}{q})^2=2$ then $q
CStudent
  • 67
0
votes
0 answers

Strong induction example from discrete math book looks like ordinary induction.

In this example, I don't see what differs strong induction from ordinary induction. If I was doing this problem with ordinary induction, I would prove the base case and then for $P\left(n+1\right)$ just like this example. Why this is considered as…
Ali
  • 45
0
votes
1 answer

Prove that for all positive integers $n........$

Prove that for all positive integers $n, 1^3+2^3+\ldots+n^3=(1+2+\ldots+n)^2$
Commander Shepard
  • 1,804
0
votes
1 answer

Proofs using wel ordering principle

Just recently , I came to knopw that mathematical induction and well ordering principle are eqivalent. b So, I'VE trying to solve this inductipn problem using WOP but haven't got anything useful except the irst few obvious things and statements…
Shreya
  • 3,035
0
votes
0 answers

Proof by induction, that $(2a-1)^n-1$ is always an even number with a > 1 and a, n being natural numbers

When I tried solving it myself I got kind of stuck at $(2a-1)^n * (2a-1) - 1$, as I haven't done any induction proof myself in a quite a while. Any help is appreciated! PS: Sorry if my formatting is wrong, this is my first post on math…
Magycyan
  • 1
0
votes
0 answers

Proof by induction of number of solutions to $m$-tuples with non-negative integers that add to a non-negative integer $n$

I have the following problem Prove by induction that there are $S(m,n) = \binom{n+m-1}{m-1}$ solutions to: $$\sum_{i=1}^m x_i = n$$ where $m \geq 1$, each $x_i$ is a non-negative integer as is $n$. Clearly, the base case $S(1,0)$ is the number of…
senri
  • 11
1 2 3
…
99 100