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

Proving strong induction implies weak induction

I have been given the following (non-predicate form) definitions for the Principle of Mathematical Induction (weak and strong,respectively) as follows: $I$: Let $U\subseteq\mathbb{N}$ with $1\in U$ and $a+1\in U$ whenever $a\in U$ , then…
Lgate8
  • 445
0
votes
1 answer

Prove by induction that if the first car stops, all of them stop

I have to prove this by induction: $n$ cars are travelling down a narrow one-way street. We know that: The distance d between each two cars is the same. The safe breaking distance b is the minimum distance between two cars that is needed for the…
ben
  • 67
0
votes
4 answers

Should be simple proof by induction

I am trying to prove $n^2>2n+1$ for $k\ge 4$. Intuitively this is true since $\lim\limits_{n\rightarrow\infty}(2+1/n)=2$. Obviously $16>9$. Assume $k^2>2k+1 \implies k^2+2k+2>2k+1+2k+2 \implies (k+1)^2+1>2(2k+1)+1$, and $2(2k+1)+1>2(k+1)+1$ so…
Burgundy
  • 2,097
0
votes
1 answer

prove the inequality by induction for the folfowing expression

1+1/2+1/3+1/4+.....+1/2^n>=1+n/2 I gOt stuck after 3rd step because I can't represent 3rd expression with the help of second one as there are other numbers between 1/2^k and 1/2^(K+1)
Arman Piloyan
  • 21
0
votes
1 answer

Prove by induction that if the first car stops, then all cars will stop

$n$ cars are travelling down a narrow one-way street. We know that: The distance $d$ between each two cars is the same. The safe breaking distance $b$ is the minimum distance between two cars that is needed for the second car to stop on time if…
question
  • 97
0
votes
1 answer

Induction problem prove that at least one of the coefficients Cn is even

For $n \in \mathbb{N}$ regard $1+x+x^2$ as a polynomial, i.e., $$(1+x+x^2)^n = \sum C_n(x^n)$$ with $C_n \in \mathbb{N}$, and prove that at least one of the coefficients $C_n$ is even. I really don't know how to solve this one I know that the sum of…
question
  • 97
0
votes
1 answer

Proof using induction Σ k+3 = n^2 / 2 + (7/2)n

So I have the following problem prove: Σ(n)(k+1) k+3 = n^2 / 2 + (7/2)n P(1) = 1 + 3 = 1^2 / 2 + 7 /2 P(1) = 4 = 4 So I assume it's true for n and attempt to prove it's true for n+1: (n+1) + 3 = (n+1)^2 / 2 + (7/2)(n+1) n+4 = (n^2 + 2n + 1) /2 +…
Jake Burns
  • 1
0
votes
1 answer

Help with induction question

I'm trying to prove the following equation by induction, but my base case isn't working. for all n>2. For my base case I did n=3, and on the LHS I got 8/9 and the RHS I got 2/3. Helppp.
ematth7
  • 719
0
votes
1 answer

Trying to correctly write the proof using *strong* induction of the sum of the nth positive integer

I'm learning about proofs using induction and our professor want us to always use strong induction when giving proofs. In my understanding, strong induction is used to show the range of numbers you have shown to be true. I want to be able to write a…
David Velasquez
  • 251
0
votes
3 answers

doubt about the solution to an induction problem exercise

I need to prove that $5^n-1$ is divisible by $4$, $\forall n \in \mathbb{N}$. So for the inductive step I know that: $$5^{n+1} -1= 5\times5^n -1$$ but how do I get from there to: $$(5^n -1) + 4\times 5^n?$$ (That is the solution to the exercise.)
O_o
  • 1
0
votes
2 answers

Induction Proof 3

I want to prove this simple fact: $\frac{n}{n+1} \geq \frac{1}{2}$ for all $n\in \mathbb{N}$. Would this suffice: Proof by induction: Base case: let $n = 1$, we have the result. Inductive step: assume that for some $k\in \mathbb{N}$ we have…
user168530
  • 161
0
votes
4 answers

Does $(p(0) \wedge (P(n) \implies P(n-1))) \implies P(n) \forall n\leq 0$?

Does $(p(0) \wedge (P(n) \implies P(n-1))) \implies P(n) \forall n\leq 0$? In other words, what I'm asking is, can I use the axiom of induction for negative numbers? Why/why not? E: This is not a duplicate from that other post, I ask nowhere about…
YoTengoUnLCD
  • 13,384
0
votes
1 answer

Strong induction on property of integers involving sets

Let property $P(n)= \begin{cases} \text{if $n$ is even, then any sum of $n$ odd integers is even} \\ \text{if $n$ is odd, then any sum of $n$ odd integers is odd} \end{cases}$ We need to show that $P(n)$ is true for all integers $n\geq2$ by strong…
user261954
0
votes
1 answer

Induction question , 0 and 1's quesiton

$010$ can be generated. If $s$ is a sequence which can be generated by these rules, then $01s, 10s, 0s1, 1s0, s01$, and $s10$ can all be generated. *Prove, by induction, that in any sequence generated by these rules, there are more $0$'s than…
Arron
  • 13
  • 2
0
votes
1 answer

Induction, 0'1 and 1's sequence fun question

010 can we generated. If s is a sequence which can be generated by these rules, then 01s, 10s, 0s1, 1s0, s01, and s10 can all be generated. -Prove (by induction?!) that in any sequence generated by these rules, there are more 0's than 1's Without…
Arron
  • 13
  • 2
1 2 3
…
99 100