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
1 answer

How to know the statement on natural numbers is univariate or bivariate for induction

In order to prove the following recurrence $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$$ It is enough to prove induction on only $n$, not needed to do induction on $r$. That is $P(0,0)$ $P(n,r) \implies P(n+1, r)$ But by seeing the…
hanugm
  • 2,353
  • 1
  • 13
  • 34
1
vote
3 answers

In the principle of Mathematical Induction, why do we take the base case as $P(1)$ only?

I kinda understand the logic and motivation behind the proof, but what bothers me is the fact, why is the base case (the first statement that we write) is always $P(1)$ when we are proving a proposition is true for all $\mathbb{N} $? Why can't it be…
William
  • 4,893
1
vote
2 answers

Cauchy's induction principle

Cauchy's induction principle states that: The set of propositions $p(1),...,p(n),...$ are all valid if: $p(2)$ is true. $p(n)$ implies $p(n-1)$ is true. $p(n)$ implies $p(2n)$ is true. How to prove Cauchy's induction principle? Can we…
Abdelrhman Fawzy
  • 456
1
vote
2 answers

$(\forall n, {\rm T} \vdash P(n)) \Rightarrow ({\rm T} \vdash \forall n, P(n))$ Why is it false?

I'm wondering why do we "need" a proof of mathematical induction. Let's $T$ be our theory and $P$ our property. $\vdash$ means that there is a proof. Thanks to induction : $\forall n$, ${\rm T} \vdash P(n)$, (so ${\rm T} \vdash P(0)$, ${\rm T}…
Melissa
  • 21
1
vote
1 answer

Proof by induction: is it enough to show 0=0?

Let $P_n$ be a proposition, so that $$P_n: 3+11+...+(8n-5)=4n^2-n$$ $P_1:3=4\cdot1^2-1$, $P_2:3+11=4\cdot2^2-2$ etc. When proving $P_n\to P_{n+1}$, is it enough to show in the second induction step that, by subtracting from both sides we have…
mechanicious
  • 413
  • 3
  • 13
1
vote
2 answers

Prove by induction that P is transitive

I'm studying Peano arithmetic and I created this problem as a challenge to myself, but I've failed. I want to prove that the following relation P, which is defined recursively, is transitive. I know that it must be proven by induction, but I can't…
user279420
1
vote
2 answers

How to prove $T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$ is $\mathcal O(n\log n)$ using induction?

How would you go about proving the recursion $$T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$$is $\mathcal O(n\log n)$ using induction? Thanks!
jenkins101
  • 11
  • 2
1
vote
1 answer

How do I find the cardinality of strings in this set?

Given a string $w \in \{1,2\}^*$, let $F(w) \in \mathbb{N}$ be the sum of all the numbers in it. For example, $F(\epsilon) = 0$ for the null string $\epsilon$, and $F(1212) = 6$. Now define some $$S_n = \{ w \in \{1,2\}^*: F(w) = n\}$$ Some…
oldselflearner1959
  • 785
1
vote
2 answers

mathematical induction with inequality

I am trying to prove by mathematical induction that $(k+3)^2 < 2^{k+3}$ for $k = 1, 2, \ldots$.
lsf456
  • 43
1
vote
2 answers

Proof by induction for systems of equations with arithmetic progression

A linear system of equations of the form $\begin{cases} ux+(u+d)y=u+2d\\ ax+(a+i)y=a+2i\end{cases}$ Will always have the solution $x=-1, y=2$ (easily proven through matrix algebra). How can I prove this by induction?
Milo Wielondek
  • 1,919
1
vote
4 answers

Prove that all positive integers $n$, $(1-{\sqrt 5})^n$ can be written in the form $a-b{\sqrt 5}$ where $a$ and $b$ are positive integers

Prove, by induction, that all positive integers $n$, $(1-{\sqrt 5})^n$ can be written in the form $a-b{\sqrt 5}$ where $a$ and $b$ are positive integers. I understand these idea of proof by induction and this was a different type of question that…
H.Linkhorn
  • 1,283
1
vote
3 answers

Solving linear recurrence by induction

Heres the "Link", my issue circled in red. Can anyone tell me how they get this this step?; How does $6s_k = 6(5^k-1)$? What rule are they using here? $s_{k+1} = 6s_k - 5s_{k-1} = 6(5^k -1)-5(5^{k-1}-1)$ Thanks everyone! -Kyle
user8258
1
vote
1 answer

Is function f a bijection? Why or why not? How to prove by induction?

I have this problem on my hands right now: Let $$f:A\to B$$ and $$g:B\to A$$ be two functions. If $$g \circ f(a) = a, \forall a\in A$$ and if $$f \circ g(b) = b, \forall b\in B$$ then $f$ is a bijection. Here are the things that are needed for $f$…
TypeR
  • 15
1
vote
3 answers

prove $2n+1 < 2^{n}$ by induction

true for base case $n = 3$, and assume true for $n=k$, then for $k \geq 3$, $$2k+1 \leq 2^{k}$$ $$2k+1 + 2 \leq 2^{k} +2$$ $$2(k+1) +1 \leq 2^{k} +2$$ since, $2^{k} +2 \leq 2^{k}\cdot2$, (requires another proof?) then, $$2(k+1) +1 \leq 2^{k} +2 \leq…
hit
  • 549
1
vote
1 answer

Is a proof by induction considered an exhaustive proof?

Say we use induction to prove a statement P(n). In my mind, induction covers every possibility for all values n, and that somewhat seems like exhaustion. Would it be wrong to say induction is some sort of abstract exhaustive proof?
kebab-case
  • 165
1 2 3
…
99 100