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

Induction Proof, $n^2$ is even $\implies$ $n$ is even

If $n^2$ is even $\Rightarrow$ $n$ is even. Test: $n = 1$. $2^2 = 4$ is even $\Rightarrow$ $2$ is even. Assuming: $P(k)$ is true with $k$ even. Test: $P(k+2)$: $k+2$ is even. I can't finish it. I do not know what to do.
John52
  • 1
0
votes
2 answers

Prove summation using induction

$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$ My basis step is $P(1)$ sets the $LHS = RHS = 1$. For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$: $$\left(\frac{(k + 1)((k + 1) + 1)}{2}\right)^2$$ But I don't…
Tim Lee
  • 51
0
votes
2 answers

What are some general rules that I can follow for mathematical induction?

Homework problems I'm currently taking a discrete math class and was hoping for some tips to solve problems that are similar to the two in the image. I've already done problem ten, but it was quite troublesome even after I watched a couple of…
False King
  • 3
  • 1
0
votes
1 answer

Simple Mathematical Induction

There is an Arithmetic Progression in such way: $a_1=1$, and for each $n\in N$, $a_{n+1}=a_n+ \frac{1}{n(n+1)}$. The problem: Prove in induction that for each $n\in N$, there exists: $a_n=2-\frac{1}{n}$. The steps of solving: Prove that it's true…
Max Ilyouchenko
  • 105
0
votes
0 answers

Induction on two statements at once

Suppose that I wanted to prove $P(n)$ is true, but I need some $Q(n)$ to be true so that I can show $P(n) \implies P(n+1)$. Is it always okay for me to do $$P(n) \land Q(n) \implies P(n+1) \land Q(n+1)$$ to show that $P(n) \land Q(n)$ are true and…
Tarang Saluja
  • 391
0
votes
2 answers

For how many values of n, will P(n) be false?

We know that $P(2018)$ is true, then surely $P(n)$ will be true for all $n>2018$. For $n<2018$, we can say that $P(2018)$ can only be true, if $P(2017)$ is true, which in-turn is true only if $P(2016)$ is true and so on... So $P(n)$ should be true…
Asad Ahmad
  • 296
0
votes
3 answers

Lower bound on a harmonic subseries

Prove that $$\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k} > \frac{1}{2}.$$ I've tried a lot of things (mainly induction) without much result. The only hint I was given was that if $a \leq c_k \leq b$ for k = 1, 2, ..., n then $na \leq…
DuckHunterZx
  • 5
0
votes
0 answers

Formulating statement $P(n)$ for mathematical induction

I need to prove that if $n \in \mathbb{N} $ and $A \subseteq I_n $, then $A$ is finite and $|A| \leq n$. Furthermore, if $A \ne I_n$, then $|A| < n$. Here, $$ I_n = \{ i \in \mathbb{Z}^+ \mid i \leq n \} $$ Since there is a natural number involved…
user9026
  • 733
0
votes
2 answers

Prove that a Tower of Height $H$ can be built if $H*(H+1)/2 = R + G$

Let us define a Red-Green Tower: Each level of the red-green tower should contain blocks of the same color. At every Increase in the level, number of blocks in that level is one less then previous level. Prove that a Red-Green Tower of Height $H$…
Het
  • 333
0
votes
1 answer

Strong induction and mistake

what is the fault in this reasoning by strong induction For all $ A $ and $ B $ of $ M_p (K) $ and all integer $n$ we have: $ A ^ n B = B $ The proof : Denote $\forall n\in \mathbb N,\quad P (n) $ : $ A ^ n B = B $ The property is true at rank…
Pascal
  • 3,771
0
votes
2 answers

Prove $(1 + 1/n)^n \le n+1$

Using principle of mathematical induction, prove that Prove the property coined $\mathcal P (n)$ $$(1 + 1/n)^n \le n+1$$ When $n =1$, $LS =2$, $RS =2$ Hence $\mathcal P (1)$ is true. Let $\mathcal P (k)$ be true Then I have to prove $$(1 + 1/k)^k…
pravakar wang
  • 11
0
votes
2 answers

For all number greater than or equal to 13, can we write this as 2x + 7y assuming x and y are non negative integers?

I'm attempting to solve this via induction So for our base case let $k = 13$ then $x = 3, y = 1$ so the base case holds Assume that for all $k$ where $ k \geq 13$ up to some integer $n$ that the claim holds s.t. they can all be written as some $2x +…
ChuChugga
  • 13
  • 4
0
votes
3 answers

How can I use induction solve this?

How can I show/solve this? I've tried by using the basis step and the inductive step, but just can't seem to get it right. $$\forall(n \geq 0)(4\mid(9^n − 5^n)).$$
Maren
  • 19
0
votes
2 answers

Induction Proof that $ x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\ldots+xy^{n-2}+y^{n-1}).$

I seek an inductive proof that $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}).$ I am stuck.
Gustavo Ortega
  • 155
0
votes
0 answers

Inductive proof on increasing coefficients

If I have two polynomials, $$a_nx^n+....+a_1x+a_0$$ and $$ b_nx^n+....+b_1x+b_0$$ and I want to show that the rate of which the coefficients are increasing, start from the $x^n$ term in the first equation is always greater than the second. For the…
argamon
  • 221
  • 3
  • 11
1 2 3
…
99 100