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

$r+r^{-1}$ integral implies $r^n+r^{-n}$ integral

Suppose r + 1/r is an integer. r is real and positve. How to prove r^n + 1/r^n is an integer by induction for all natural numbers n.
Steve
  • 63
2
votes
2 answers

Proof by induction for divisibility by power of 2^n

I'm trying to prove, using strong induction, that $2^n$ divides $a_{n}$ where: $$a_{n} = 2a_{n-1} + 4a_{n-2}$$ Given that $a_{1} = 2$ andn $a_{2} = 8$ What I've got so far: Base Case $$n = 1$$ $$a_{1} = 2$$ $$2^{1} | 2$$ $$n = 2$$ $$a_{2} =…
Hugo
  • 45
2
votes
7 answers

$7\mid 2\cdot8^n+3\cdot15^n+2$ is divisible by 7?

I tryed a lot of ways to prove that and I can't. My formula is: $$ 2\cdot8^n+3\cdot15^n+2 $$ And I need to prove if is divisible by 7. Recently I got: $$ 2\cdot8^1+3\cdot15^1+2 $$ $$ 63 $$ And with K+1 is: $$ 2\cdot8^{k+1}+3\cdot15^{k+1}+2 $$ $$…
jtwalters
  • 155
2
votes
1 answer

Proving a Summation Equation by Induction

Prove this by induction: $$\sum_{i=1}^n i(i!) = (n+1)!-1$$ So I wrote: Base Case: $n=1$ so $1(1!) = 1$ and $(1+1)!-1 = 1$. Let $n=k$ so that $$\sum_{i=1}^ki(i!)=(k+1)!-1$$ $n=k+1$ $$\sum_{i=1}^{k+1}i(i!)=((k+1)+1)!-1$$ But I'm stuck here. Also…
Adam
  • 223
2
votes
2 answers

Some rather non-traditional forms of mathematical induction.

The definition of induction that most of us are familiar with is this: If statement $S$ is true for $1$, and $$S \text{ is true for } n\implies S \text{ is true for }n^+$$ then $S$ is true for all natural numbers. This is the only kind of induction…
algebraically_speaking
  • 197
2
votes
3 answers

Mathematical induction proof that $8$ divides $3^{2n} - 1$

I'm struggling with this question: prove the following using simple mathematical induction. $$ 8 \mid (3^{2k} - 1) $$ What I've got so far is: $$ 3^{2k+2} - 1 = 3^{2k} \cdot 3^{2} - 1 $$ From here, I'm not entirely sure where to go, please advise.
Hugo
  • 45
2
votes
2 answers

Proving an inequality using induction

Use induction to prove the following: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^n}\geq1+\frac{n}{2}$ What would the base case be? Would it still be $n=0$ so $\frac{1}{1}+\frac{1}{2}\geq 1+\frac{0}{2}$, which holds true. then how would…
cooltrainer
  • 105
2
votes
1 answer

Prove by induction that $\sum_{i=0}^n \left(\frac 3 2 \right)^i = 2\left(\frac 3 2 \right)^{n+1} -2$

Prove, disprove, or give a counterexample: $$\sum_{i=0}^n \left(\frac 3 2 \right)^i = 2\left(\frac 3 2 \right)^{n+1} -2.$$ I went about this as a proof by induction. I did the base case and got the LHS = RHS. When I went to show $P(k) \implies…
Vincent
  • 2,329
2
votes
2 answers

is it wrong to do this to solve an induction question

When doing an induction problem is it wrong to simply add the next variable to both sides? for example for all natural numbers $$4+9+14+19....+(5n-1)=\frac{n}{2}(3+5n)$$ assume true for k $$4+9+14+19....+(5k-1)=\frac{k}{2}(3+5k)$$ is it wrong to do…
user128922
  • 113
2
votes
2 answers

Can someone help me with this proof?

Prove that $$1^2-2^2+3^2...+(-1)^{n-1}n^2=(-1)^{n-1}\frac{n(n+1)}{2}$$ whenever $n$ is a positive integer. I used $2$ as my base case and it worked. Then I plugged in $k$ for $n$. Now I can't figure out how to do the $k+1$ step. I would greatly…
user128922
  • 113
2
votes
2 answers

PROVE if $x \ge-1 $then $ (1+x)^n \ge 1+nx $ , Every $n \ge 1$

Use mathematical induction to prove this. Here is my answer but I stuck at certain point. Base Case: n=1 $$(1+x)^1 \ge 1+x $$ True , Induction Case: n=k assume $$(1+x)^k \ge 1+kx $$ n=k+1 $$ (1+x)^k+1…
hacikho
  • 53
  • 7
2
votes
3 answers

Using Induction, prove that $107^n-97^n$ is divisible by $10$

Using Induction, prove that $107^n-97^n$ is divisible by $10$ We need to prove the basis first, so let $ n = 1 $ $107^1-97^1$ $107-97 = 10$ This statement is clearly true when $ n = 1 $ Now let's use $P(k)$ $107^k-97^k$ So far so good... next I…
usukidoll
  • 2,074
2
votes
4 answers

For $n \geq 2$, prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$

For $n \geq 2$ prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$ We need to use induction. The Principle of Mathematical Induction, Theorem 4.2.1, states that $n_0 \in \mathbb{Z}$. For each integer…
usukidoll
  • 2,074
2
votes
2 answers

How to prove by induction

How to prove by induction? For $n\ge 1$: $\sum_{j=n}^{2n-1} (1/j) = \sum_{k=1}^{2n-1} ((-1)^{k+1}/k)$ 1) Base case $\sum_{j=1}^{1} (1/j) = 1 = \sum_{k=1}^{1} ((-1)^{k+1}/k)$ 2) Induction [Prove that $\sum_{j=n+1}^{2(n+1)-1} (1/j) =…
SJKK
  • 23
2
votes
3 answers

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$

Use induction to prove $2n + 1 \le 2^n$ for $n=3,4,\ldots$ I've plugged $3$ in for $n$ I get $7 \le 8$ then I set $2(n+1) +1 \le 2^{n+1}$ then I'm lost.
Jack
  • 47
1 2 3
…
99 100