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

Induction over the natural numbers

I need to prove, by induction, that for all $n$ there exists an $m$ with the property that $$m^2 \leq n \leq (m+1)^2$$ I can easily establish a base case (picking $n = m = 0$). I am finding it harder to assume this property holds and find an $m$…
Victoria
  • 365
4
votes
2 answers

Induction question

I have to prove that $$P(n):\quad 1^2-2^2+3^2-\dots+(-1)^{n+1}n^2=(-1)^{n+1}T_n$$ where $T_n=1+2+\ldots+n=\frac{n(n+1)}{2}$. I know I have to solve by induction. So, I showed a base case that when $n=1$, then $P(1)$ is true. And then I…
ematth7
  • 719
4
votes
5 answers

How do you prove $37^{100} - 37^{20}$ is a multiple of $10$ using induction?

I've tried making it $37^{5n} - 37^n$ is a multiple of $10.$ Then I made the base case be $n = 0,$ so $1 - 1 = 0$ which is a multiple of $10.$ I assumed $37^{5n} - 37^n$ is a multiple of $10$ for all $n \geqslant0.$ The inductive step is really hard…
user88528
4
votes
3 answers

Trapped in Induction, how to get out?

Example 1: Prove by induction that $1+3+5+...+(2n-1)=n^2 \text{ for all } n \in \mathbb{N}....(*)$ Proof: Step 1: For $n=1$, left-side we have $(2(1)-1) = 1$. Right-side we have $(1)^2 = 1$. Step 2: Suppose (*) is true for some $n=k \in \mathbb{N}$…
lucidgold
  • 1,054
4
votes
5 answers

Prove using mathematical induction that $x^{2n} - y^{2n}$ is divisible by $x+y$

Prove using mathematical induction that $(x^{2n} - y^{2n})$ is divisible by $(x+y)$. Step 1: Proving that the equation is true for $n=1 $ $(x^{2\cdot 1} - y^{2\cdot 1})$ is divisible by $(x+y)$ Step 2: Taking $n=k$ $(x^{2k} - y^{2k})$ is…
Jacqueline Collette
  • 75
  • 1
  • 1
  • 6
4
votes
2 answers

Closed knight's tour

I know what a 3x10 looks like, but I cannot seem to find a distinguishable pattern to extend it to a 3x14. The 3x10 pattern I'm using looks like the one at the top right of figure 6 of this paper. Any help would be greatly appreciated.
fossdeep
  • 239
4
votes
1 answer

Proving mathematical induction with arbitrary base using (weak) induction

I attempted a proof of mathematical induction using an arbitrary base case, but was unsuccessful (and hence this question). Below is what I was trying to do and along with my thinking; if anyone can point me in the right direction I'd appreciate…
russell11
  • 43
4
votes
3 answers

How to prove a sum of series

How do I prove that for any natural number $n$ we have $$\sum_{i=0}^n i^4 \neq \left(\sum_{i=0}^n i\right)^3?$$ Any help would be greatly appreciated.
Ian Moon
  • 41
4
votes
4 answers

Proof by induction $\frac1{1 \cdot 2} + \frac1{2 \cdot 3} + \frac1{3 \cdot 4} + \cdots + \frac1{n \cdot (n+1)} = \frac{n}{n+1}$

Need some help on following induction problem: $$\dfrac1{1 \cdot 2} + \dfrac1{2 \cdot 3} + \dfrac1{3 \cdot 4} + \cdots + \dfrac1{n \cdot (n+1)} = \dfrac{n}{n+1}$$
user3989
4
votes
7 answers

Use mathematical induction to prove that for all integers $n \ge 2$, $2^{3n}-1$ is not prime

I had a homework due yesterday with this problem. The TA did the problem last week in discussion but I didn't understand it. She pulled out a $7k$ almost immediately, and I have no idea from where. It was like, it wasn't prime if $2^{3n}-1$ was 7…
user13327
4
votes
1 answer

Show that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction

Is the following a correct way of showing that $n^3 > (n+1)^2$ for $n>2$ using mathematical induction? Thank you in advance! $P(n): n^3>(n+1)^2$ $P(3): 3^3>(3+1)^2$ $27 > 16$ (correct) $P(k): k^3>(k+1)^2$ Assume $P(k)$ is true. $P(k)$ $\implies$…
user190290
4
votes
4 answers

Equilateral triangle is cut in $4^n$ congruent equilateral smaller triangles

I have an assignment on proof by induction: Suppose $n$ is a positive integer. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. (Figure $1$ shows an example with $n = 2$). Show that the…
user168764
3
votes
2 answers

Use induction to prove that $n^3 + (n+1)^3 + (n+2)^3 $ is divisible by $9$

Prove that for all integers $n\geq 0, n^3 + (n+1)^3 + (n+2)^3 $ is divisible by 9. If $ n=1, 1+8+27 = 36 = 9 * x $ Suppose $ n = k, k^3 + (k+1)^3 + (k+2)^3 $ is divisible by 9. Find out $ n = k + 1, $ is divisible by 9. Because $2$ is divisible by…
Q123
  • 251
3
votes
3 answers

Prove by Induction : $n < 2^n$

So I need to prove the inequality : $$n < 2^n$$ by Induction. What I have done so far is : Step $1$: Prove that the statement is true for $n=1$ $$1<2^1$$ (true) Step $2$: Prove that, if $p(n)$ is true, then $p(n+1)$ is also true. Assume that…
FarahFai
  • 161
  • 9
3
votes
2 answers

Prove that in a bit string, the string 01 occurs at most one more time than the string 10.

Good morning. This is my first question in a StackExchange forum. Let me know if I'm doing anything incorrectly (posting in the wrong forum, etc.). Prove that in a bit string, the string 01 occurs at most one more time than the string 10. I wish to…
favq
  • 2,816
1 2 3
…
99 100