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
3
votes
3 answers

How to prove $n=7k$ or $7k+1$, if $n=x^2=y^3$.

$n$ is both a square and a cube, I need to prove $n=7k$ or $n=7k+1$, for some integer $k$. I need some guide lines.
Wes
  • 497
3
votes
1 answer

Understanding induction in constructing an injection from $\mathbb{N}$ to an infinite set

I've been working on a proof that states if $X$ is an infinite set, then there exists an injection $f: \mathbb{N} \to X$. Here is the proof I came up with: Let $X$ be an infinite set. We will construct the injection $f: \mathbb{N} \to X$…
Noah
  • 55
  • 2
3
votes
0 answers

Writing down the induction principle formally

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)? $$(\exists x\in\mathbb {N}(P (x))\wedge \forall y\in \mathbb {N}_{\geq x}(P (y)\Rightarrow P…
Constantine
  • 1,429
3
votes
4 answers

using induction to prove $(n+1)^2 < 2n^2$

(Im not English and just started doing maths in English so my termiology is still way off) So the title for $n\ge 3$ First I use calculate both sides with $3$, which is true I make my induction. $(k+1)^2 < 2k^2$ then I replace $N$ with $k+1$: …
Wouter Zirkzee
  • 33
  • 2
3
votes
1 answer

why is a vacuously true base case valid for simple induction?

I am self-teaching and am doing the now-famous Tao Analysis I exercise 2.2.5 which guides us to use weak induction to prove strong induction. Many of the solutions on this site, and elsewhere, use then notion of a vacuously true base case for the…
Penelope
  • 3,147
3
votes
2 answers

Proof by induction that $n!\gt 2^{n}$ for $n \geq 4$

$n!\gt 2^{n}$ for $n \geq 4$. Then there is an inductive proof: We assume that $n! \gt 2^{n}$ for every random $n \in \mathbb{N}$ with $n\geq4$, and we need to proof that $(n+1)!\gt 2^{n+1}$. Because $(n+1)\gt0$ and $n!\gt2^{n}$, it follows that…
Garth Marenghi
  • 1,115
3
votes
5 answers

What do we assume when we do proof by induction?

I am having a little confusion when we do proof by induction. Lets start off with this, if I knew $(\forall x \in \mathbb{R} f(x) = 1)$, then I know that $(\forall y \in \mathbb{R} f(y) = 1)$ (and vice versa), so we can write $(\forall x \in…
Nav Bhatthal
  • 1,057
3
votes
2 answers

Interpretation in notation for making a proof and substitution processes

It is asked to be prove: $$\forall{n}\in{N}:(n+1)(n+2)(n+3)...(n+n)=2^n\cdot1\cdot3\cdot5...\cdot(2n-1)$$ 1 Step p(n) is assumed to be true for n=1 $$(n+1)(n+2)(n+3)...(n+n)=2^n\cdot1\cdot3\cdot5...\cdot(2n-1)$$ Meaning that it is only consider the…
Haizum Skallah
  • 653
3
votes
3 answers

Proof by induction: Why am I wrong?

I have this exercise where I am a little stuck. Proof the following statement: For all $n \in \mathbb{N}$ show that $\sum_{i=1}^n \frac{1}{i(i+1)} = 1 - \frac{1}{n+1}$ Proof. Base case: Let $n=1$. $\sum_{i=1}^n \frac{1}{i(i+1)} = \frac{1}{1(1+1)} =…
fjg
  • 33
3
votes
0 answers

Prove that $a_n = 2^{n+1}-1$ for all whole number $n \ge 0$

I have the sequence: $$ \begin{cases} a_0=1 \newline a_n = 2a_{n-1}+1, n \ge 1 \end{cases}$$ And I want to prove that $a_n = 2^{n+1}-1$ for all whole number $n \ge 0$ I started by calculating $a_0,a_1,a_2$ and…
Firellsp
  • 117
3
votes
5 answers

Use weak induction to prove the following statement is true for every positive integer $n$: $2+6+18+\dots+2\cdot 3^{n-1}=3^n-1$

Use weak induction to prove the following statement is true for every positive integer $n$: $$2+6+18+\dots+2\cdot 3^{n-1}=3^n-1$$ Base Step: Prove it is true for $n$. Inductive Hypothesis: It will be true for $n+1$ What I need to show: That it will…
Natasha
  • 333
3
votes
3 answers

Show that the postage of six cents or more can be achieved by using only 2-cent and 7-cent stamps by using strong induction.

Show that the postage of six cents or more can be achieved by using only 2-cent and 7-cent stamps by using strong induction. I know the important step to keep in mind is: Induction step: If $P(m), P(m+1), P(m+2) \ldots P(k)$ is true then $P(k+1)$ is…
Natasha
  • 333
3
votes
1 answer

Show that the set can describe all rational numbers in (0, 1).

Let A be a subset of (0, 1) ∩ Q, where Q is the set of all rational numbers. Given that $\frac{1}{2}\in A$ and that $\frac{x}{x+1},\frac{1}{x+1}\in A$ if $x\in A$, show that A = (0, 1) ∩ Q. What I've tried to do: For simplicity, let (1) be the…
Stanislav Brega
  • 33
3
votes
2 answers

Why is induction considered reliable and fool proof?

I'm in high school, learning induction Apparently, induction requires the satisfaction of two steps The initial or base case: prove that the statement holds for 0, or 1. The induction step, inductive step, or step case: prove that for every n, if…
James Da Silva Chen
  • 61
3
votes
1 answer

Poker Circles Induction

Mehcad plays poker against 2n players already arranged in a circle. He will lose $1$ dollar against the ones better than him (wearing red shirts) but win $1$ dollar against ones weaker than him (wearing blue shirts). There are n red shirts and n…
serendipity0217
  • 187
1 2 3
…
99 100