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

Prove expression is not prime

$$ (n + 4)^4 + 4 $$ If n is natural number, how to prove that above expression is not prime? I am stuck here $$ (n+4)^2 \cdot (n+4)^2 + 2 . 2 $$ $$ \left(\left(n^2+4^2\right) \cdot 2\right)\left(\left(n^2+4^2\right) \cdot 2\right) $$
kdebugging
  • 145
3
votes
2 answers

Proving $\sum_{i=1}^{n} {\frac{1}{4i^2-1}} = \frac{n}{2n +1}$ for all $n \in N$ using mathematical induction

I'm having a horrible time completing this since this is the first time I'm learning mathematical induction. So far I have this: Let $P(n)$ be: $P(n):\sum_{i=1}^{n} {\frac{1}{4i^2-1}} = \frac{n}{2n +1}$ For the base case, $n=1$ $LHS = \sum_{i=1}^{0}…
lxkmxl
  • 43
3
votes
2 answers

Reason behind particular induction step

I'm wondering why and how you get some of these steps in an Induction proof. Okay, so the question is to prove the following statement by induction: $1 - x + x^2 - x^3$ $+ ... +$ $x^{2n-2} = \frac{x^{2n-1}+1}{x+1}$ The first step that sort of…
atb
  • 285
  • 3
  • 10
3
votes
1 answer

Prove by mathematical induction

Prove the following statement by using mathematical induction: $3+8+ ··· + (n^2 − 1) = \frac{1}{6}n(n − 1)(2n + 5)$, for all integers $n ≥ 2$. After making a common factor $\frac{1}{6}k$ and expanding I'm left with…
RM1973
  • 89
3
votes
4 answers

Prove that $(\sum_{i=1}^n i)^2$ = $\sum_{i=1}^n i^3$ by induction

Prove that: $(\sum_{i=1}^n i)^2$ = $\sum_{i=1}^n i^3$ I can use the fact that $\sum_{i=1}^n i$ = n(n+1)/2 after the inductive hypothesis is invoked. I'm not sure where to start, I would usually break down one side but there isn't usually two sums,…
JanoyCresva
  • 486
  • 7
  • 18
3
votes
1 answer

Induction on $2^n > n^2 - 7$.

I am trying to prove, by induction, that $2^n > n^2 - 7, \forall n \in \mathbb{N}$. I am stuck in the inductive step: $n = n+1$. $$\begin{align*} 2^{n+1} &= 2 \cdot 2^n \\ &> 2 \cdot (n^2 - 7) \tag{By I.H.} \\ &= 2 \cdot (n^2 + 2n + 1 - 10) \\ &=…
mnk888
  • 195
3
votes
4 answers

$2 \cdot 4^{2n + 1} + 3^{3n + 1}$ is divisible by $\lambda$, for all $n \in N$. Find $\lambda$.

I'll state the question here: If "$P(n): 2 \cdot 4^{2n + 1} + 3^{3n + 1}$ is divisible by $\lambda$, for all $n \in N$" is true, then what is the value of $\lambda$? This is what I can think of: $P(1): 2 \cdot 4^{2(1) + 1} + 3^{3(1) + 1}$ is…
Shinsekai no Kami
  • 484
  • 4
  • 15
3
votes
2 answers

How to prove induction when n is part of the sum

How to Prove $$\sum_{k=1}^{2n} (-1)^{k-1}\frac{1}{k} = \sum_{k=1}^{n}\frac{1}{k+n}$$ by induction we did a few of induction but the n was never a part of the sum so im kinda lost on where to start because if I would try to use n+1 i have no idea how…
Chaos
  • 33
3
votes
1 answer

Simple Induction vs Strong Induction proof.

I am having a great deal of trouble grasping the essential difference between Simple induction and Strong Induction proof. I was hoping someone here would do me the honor of making an example. First illustrating simple induction then the same…
Nulle
  • 197
3
votes
1 answer

Unusual induction question

Prove that $1^n + 2^n + . . . + (n − 1)^n$ is divisible by n if n is odd. I tried using induction. I finished the base case and then the assumption, but then I couldn't substitute in the assumption like other induction questions because the exponent…
Gerard L.
  • 2,536
3
votes
5 answers

Show that $\sum^{n}_{k=1}(k+2)(k+4) = \frac{2n^{3} + 21n^{2} + 67n}{6}$

When doing induction should you always try to put your final answer as the "desired " form? For example if: $$\sum^{n}_{k=1}(k+2)(k+4) = \frac{2n^{3} + 21n^{2} + 67n}{6}$$ we ought to give the final answer as $$\frac{2(k+1)^{3} + 21(k+1)^{2} +…
user376984
  • 221
3
votes
4 answers

$2^n > n^4$ proof by induction

This is what I came up with so far: Inductive step: assume $2^n > n^4$. Need to prove $2^{n+1} > (n+1)^4$ $$ 2^{n+1} = 2 \cdot 2^n > 2 \cdot n^4\\ (2 \cdot n^4)^{1/4} = (2)^{1/4} \cdot n > n+1 \implies 2n^4 > (n+1)^4 \implies 2^n > (n+1)^4 $$ Is…
JJTO
  • 141
3
votes
5 answers

Use the PMI to prove the following $4^{k}-1$ is divisible by 3.

$4^{n}-1$ is divisible by $3.$ (i) Basis Step: $P(1)$is true because $4^1 -1=3 $ and $3\mid3$. (ii) Suppose $P(k)$ is true for induction hypothesis $3\mid4^{k}-1$. Show $(k+1)$ is true $3\mid4^{k+1}$ Now here is where things gets…
Jon
  • 1,920
3
votes
2 answers

Prove that $(n!)^2 ≥ n^n$ using mathematical induction

1° $n_0=1$ $(1!)^2 \ge 1^1$ $1\ge1$ 2° $k \ge n_0$ assumption: $$(k!)^2 \ge k^k$$ and for k+1: $$((k+1)!)^2 \ge (k+1)^{k+1}$$ I also noticed that: $$((k+1)!)^2 = (k!)^2 * (k+1)^2$$
Overkillus
  • 104
3
votes
1 answer

Double induction - another method?

I am going through some good old Fibonacci proof by induction problems that require two counters $m, n$ instead of one. In order to prove $P(m, n)$ for all $m,n \in \mathbb{N}$, I am thinking of first proving $P(0, 0)$ and then proving that…
Yiyuan Lee
  • 14,435
1 2 3
…
99 100