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

Proof using mathematical Induction

Suppose I am proving the statement $P(m,n)$ in natural numbers. Steps: 1) Proving $P(1,1)$ true 2) $P(m,n) \implies P(m+1,n)$ My doubt while proving second step is that, can I assume $P(m,1), P(m,2),\cdots P(m,n)$ are true or I have to prove by…
hanugm
  • 2,353
  • 1
  • 13
  • 34
2
votes
1 answer

Proof by induction on $r$ variables

If there is a statement $P(n)$, proof by induction has three steps. Base case is to show $P(1)$ is true Induction step is to assume $P(K)$ is true and then to show $P(k+1)$ is true. If our statement $P(n_1,n_2,n_3,\cdots, n_r)$ involves $r$…
hanugm
  • 2,353
  • 1
  • 13
  • 34
2
votes
3 answers

Prove by induction $\sum_{i=1}^n 3i(i+4) = \frac{(n)(n+1)(2n+13)}{2}$

In this problem I have to prove the following equation using mathematical induction: $$\sum_{i=1}^n 3i(i+4) = \frac{(n)(n+1)(2n+13)}{2}$$ So far I've proved that $P_1$ is true, and written $P_k$ as $$15+36+63+...+3k(k+4)=…
Pablo
  • 548
2
votes
2 answers

How to use mathematical induction to verify: $\sum_{i=1}^{n}\frac{1}{i(i+1)} = \frac{n}{n+1}$

How to use mathematical induction to verify: $\sum_{i=1}^{n}\frac{1}{i(i+1)} = \frac{n}{n+1}$ I have already tried it myself: see here but it is just not working out... Thanks in advance!
Noah Cardoza
  • 31
2
votes
1 answer

Prove using induction that $n^3 − n$ is divisible by 6 whenever $n > 0$.

Prove using induction that $n^3 − n$ is divisible by $6$ whenever $n > 0$ My attempt: Base step: For $n=1$ $1^3 - 1 = 0$. $0$ which is divisible by $6$. Thus, $n= 1$ is true. Assumption step: Let $n=k$ $k^3-k$ Inductive step:…
user495188
2
votes
2 answers

Prove that $ a^n + b^n + c^n = d^n + e^n + f^n $ by induction

If $a,b,c,d,e,f$ are six real numbers such that: $$ a + b + c = d + e + f $$ $$ a^2 + b^2 + c^2 = d^2 + e^2 + f^2 $$ $$ a^3 + b^3 + c^3 = d^3 + e^3 + f^3 $$ Prove by mathematical induction that: $$ a^n + b^n + c^n = d^n + e^n + f^n $$ I tried…
Shukant Pal
  • 231
2
votes
2 answers

Every natural number n greater than or equal to 6 can be written in the form n = 3k +4t for some k,t in N

Prove by strong induction that every natural number $n \geq6$ can be written in the form $n=3k+4t$ for some $k,t \in \mathbb{N}$. I'm not entirely comfortable with the concept of strong induction. I believe you assume that $P(1), P(2), P(3),...…
AustereTiger
  • 236
2
votes
2 answers

Induction Step Subtleties

I've noticed something about students versus more mathematically mature people when using induction. When we assume a statement is true for some $k$, i.e. $P(k)$ is true, we then proceed directly from $P(k)$ to $P(k+1)$. Whereas I've noticed in…
Evan
  • 55
2
votes
4 answers

Prove by induction that $n^2>7n+1$ for all $n \ge 8$

So in my math book I came across this proof by induction. It states: Example Prove that $n^2>7n+1$ $\forall n\ge8$ Solution The result is true when n=8 because $8^2=64$ and $7*8+1=57$. Suppose it is true when $n$ is any number $k\ge8$ that is…
Viktor Lindblad
  • 33
  • 4
2
votes
1 answer

Proof by induction verification

I think I'm using what I'm trying to prove in the induction step. To prove is $\sum_{k=1}^nk(n-k)=\frac{(n-1)n(n+1)}{6}$. My induction step…
user515599
2
votes
2 answers

$(a+b)^n < 2^n(a^n + b^n)$ when $ a,b>0$ will it be possible for n

$(a+b)^n < 2^n(a^n + b^n)$ when $ a,b>0$ will it be possible for all natural number . How to proceed with it by Mathematical Induction? can anyone help me?
cmi
  • 3,371
2
votes
5 answers

Prove using Mathematical Induction that $2^{3n}-3^n$ is divisible by $5$ for all $n≥1$.

I did most of it but I stuck here I attached my working tell me if I did correct or not thanks My working: EDITED: I wrote the notes as TEX Prove using induction that $2^{3n} - 3^n \mod{5} = 0$. Statement is true for $n = 1$: $$2^{3 * 1} - 3^1 =…
Alastair Micallef
  • 33
2
votes
3 answers

Induction $n\ge 0, n^2-n$ is even

I am stuck trying to get the inductive step done on the following proof... For all $n \ge 0, n^2 - n$ is even. I have established that the problem is even by setting it equal to $2k$ and then plugging in $n+1$ but after that I am stuck. Proof:…
user503376
2
votes
2 answers

Recursive induction

Question: Let the set $S$ be defined recursively as follows: Basis Step: $(0,0,2)\in S$ Recursive Step: If $(a,b,c)\in S$, then $(a+1,b+1,c)\in S$ and $(a+1,b,c+1) \in S$ Use structural induction to prove that $a+b+c$ is even when $(a,b,c) ∈…
Ravnesh Kumar
  • 23
  • 3
1 2 3
…
99 100