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

Prove by induction: If $h$ and $k$ are any two distinct integers, then $h^n-k^n$ is divisible by $h-k$.

If $h$ and $k$ are any two distinct integers, then $h^n-k^n$ is divisible by $h-k$. Let's start with the basis. Let $n=1$, then $h^1-k^1 = h-k$ Now for the induction, I can't use $k$ because I don't want to be confused. So let $P(r)$ for $h^n-k^n$…
usukidoll
  • 2,074
1
vote
1 answer

Show $0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}$ by induction

Show that if $0\leq x < n, n \geq 1$, and $n\in\mathbb{N}$ then $$ 0 \leq e^{-x} - \left( 1 - \frac{x}{n} \right)^n \leq \frac{x^2e^{-x}}{n}. $$ By using induction. Progress: Decided to split the problem up into two parts, (i) and (ii). (i) $ 0 \leq…
liedora
  • 87
1
vote
1 answer

Induction: $\frac{n!}{x(x+1)\cdots(x+n)} = \binom{n}{0}\frac{1}{x}-\binom{n}{1}\frac{1}{x+1}+\cdots+(-1)^n\binom{n}{n}\frac{1}{x+n}$

$$\frac{n!}{x(x+1)\cdots(x+n)} = \binom{n}{0}\frac{1}{x}-\binom{n}{1}\frac{1}{x+1}+\cdots+(-1)^n\binom{n}{n}\frac{1}{x+n}, \quad \text{for } x \not \in \{0,-1,-2,\dots,-n\}$$ Can somebody please help me with this? I tried to multiply both sides with…
eudoxyz
  • 128
1
vote
0 answers

There are 10 non distinguishable balls and one of these has different weight

There are 10 non distinguishable balls and one of these has different weight(one does not know whether it is weigh more or less than others). One can use scales 3 times to compare their weight. You can easily show that starting with comparing 2 sets…
user112018
  • 941
1
vote
3 answers

Simple induction proof that $3^n + 5^n \ge 2^{n+2}$

Im having a lot of trouble proving by induction that $3^n + 5^n \geq 2^{n+2}.$ The base step is easy, but I don't seem to find the way to proof the inductive step.
FranckN
  • 1,304
1
vote
4 answers

Proof for maths induction

prove: $$ \sum_{r=1}^{n}[r^{2}+1](r!)=n[(n+1)!]$$ for all $n \in N$ prove $n=1$, $(1^2+1)(1!)$ = $1[(1+1)!]$ assume true for $n=k$, $(k^2+1)$$(k!)$= $k$$[(k+1)!]$ I got to here : $[k^{2}+1](k!)+[(k+1)^2+1](k+1)! = (k+1)[(k+2)!]$
luke
  • 45
1
vote
2 answers

structural induction

prove by structural induction that in any tree T, the number of leaves is 1 more than the number of nodes that have right siblings. My proof so far: s(n). in any tree T, the number of leaves(L) is 1 more than the number of nodes(N) that have right…
None
1
vote
1 answer

Proof by induction past exam question attempt

I am revising for an exam that is later today. I'm attempting all questions on past papers. Proof is a topic i've had difficulty with, if someone could check over my answer and give me some improvements for full marks, that'd be fantastic. Sorry…
user120993
  • 13
1
vote
2 answers

Induction proof equivalence

In Induction, we do the following: Check $P(1)$ is true, then show that if $P(k)$ is true, then $P(k+1)$ is also true. So we proceed to assuming $P(k)$ is true, then attempt to show $P(k+1)$ is true, as the inductive hypothesize. But are we allowed…
Lemon
  • 12,664
1
vote
4 answers

Prove that $ n^3 + 5n$ is divisible by 6 for all $n\in \textbf{N}$

Prove that $ n^3 + 5n $ is divisible by 6 for all $ n \in \textbf{N} $. I provide my proof below.
William Muenzinger
  • 716
1
vote
1 answer

Question about mathematical induction

Given $a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$, $a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$, $a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n\ge2$ where $a>0$ and $A>0$; prove that $$ {a_n-\sqrt{A} \over a_n+\sqrt{A}} = \Big({a_1-\sqrt{A} \over a_1 +…
Vibha
  • 31
1
vote
2 answers

Prove that $(x_{n})$ is bounded above by $4$

Let, $(x_{n})$ be a sequence define recursively by, $x_{1}=1$ and $x_{n+1}=\frac{1}{2}(x_{n}+\sqrt{3x_{n}})$. Verify that the sequence is bounded above by 4. By induction we have: for $n=1$, $ x_{1}=1<4$. Now suppose that $x_{n}<4$ is true for…
user24047
1
vote
3 answers

Divisibility Mathematical Induction Help

Could you please help me with this question prove that $\displaystyle5^n + 2\cdot(11)^n$ is a multiple of $3$. Thanks
alee18
  • 83
1
vote
2 answers

Prove or disprove that every Boolean function can be expressed by using only the operator ↓

I know that the ↓ operator means "nor" but how do I prove/disprove that every Boolean function can be expressed using only this operator ? Induction ? Contradiction ? I have to idea where to begin. Help would be much appreciated.
kiasy
  • 127
1
vote
1 answer

Proof by Mathematical Induction

7a. Prove by Mathematical Induction that $4^{n+1}+5^{2n-1}$ is divisible by $21$.
display_name
  • 143
1 2 3
…
99 100