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

Prove that $\frac{n}{2}$ < 1 + $\frac{1}{2}$ + $\frac{1}{3}$ + ... + $\frac{1}{2^n-1}$ < n for every n $\in \Bbb{N}$, n > 1, by using induction.

The basis checks out, and if we assume that the statement holds for n, we have to prove that it also holds for $n+1$: $$\frac{n+1}{2} < 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{2^n-1} + \frac{1}{2^n} + \frac{1}{2^n+1} + ... +…
Mračna Seka
  • 115
4
votes
1 answer

Proof by induction on two variables (forward and backward at the same time?)

Function $f(t,n,m)$ is defined for $0\le t \le T$, $n\in\{0,\ldots\}$ and $m\in\{2,\ldots\}$. We would like to show some properties are true for any $t$ and all $n$ and $m$. I thought perhaps I can show this by induction. So I started by the base…
user1007034
4
votes
1 answer

Basic Induction with Sigma Manipulation

what is the approach in this example: I checked four inputs from zero to 3(included) and got the same output for all of them: 0,1,9,36. I guessed the law that stands behind it, which is: So i proved the Base Case for n = 1, and assumed Hypothesis…
Mabadai
  • 369
4
votes
2 answers

if $S_n = (3 + \sqrt{5})^n + (3 - \sqrt {5})^n$ then show that $S_n$ is an integer by induction

this is all that i have tried: let $n=1$ so equation gives $(3 + \sqrt {5}) + (3 - \sqrt {5}) = 6$ which is an integer so it is true for $n=1$ now let it be true for $k \ge n$ then we have: $(3 + \sqrt {5})^k + (3 - \sqrt {5})^k$ is an integer for…
AYUSHROCKS123
  • 83
4
votes
1 answer

Multiplication function with sets

Prove there is a unique function $$* :\mathbb N \times \mathbb N\to\mathbb N$$ such that: $m * 0 = 0 $ for all $m \in \mathbb N$ $m * (n+1) = m * n + m$ for all $m,n \in \mathbb N$
sarah jamal
  • 1,463
4
votes
2 answers

Base Case Strong Induction Terrence Tao question

Terrence Tao formulates strong induction as follows: "(Strong principle of induction). Let $m_o$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number . Suppose that for each $m \geq m_0$, we have the following…
JCAL
  • 234
  • 1
  • 12
4
votes
0 answers

Proof by induction that $\frac{1}{1\times2} + \frac{1}{2\times3} + ... + \frac{1}{n(n+1)} < 1$ for all integers $n \geq 1$.

I am attempting to prove by induction that $\frac{1}{1\times2} + \frac{1}{2\times3} + ... + \frac{1}{n(n+1)} < 1$ for all integers $n \geq 1$. I have been able to show (using a telescoping sum) that the LHS is equal to $1 - \frac{1}{n+1}$, which is…
1123581321
  • 954
4
votes
2 answers

Prove by induction that $1*3+2*3^2+3*3^3 + \cdots + n*3^n = \dfrac{3}{4}(3^n(2n-1)+1)$

I'm trying to prove this using induction $1*3+2*3^2+3*3^3 + \cdots + n*3^n = \dfrac{3}{4}(3^n(2n-1)+1)$ So far I have: Base case: true Induction step: $\dfrac{3}{4}(3^n(2n-1)+1)+(n+1)*3^{n+1}=\dfrac{3}{4}(3^{n+1}(2(n+1)-1)+1)$ here is where I get…
krneki
  • 97
4
votes
3 answers

Need help with this proof via induction

Let $x_1,...,x_n > 0$. I'm having troubles proving this formula via induction: $$ (x_1 + \ldots + x_n)\left(\frac1{x_1} + \ldots + \frac1{x_n}\right) \ge n^2 $$ So far, I've managed to rewrite it like this: $$ \sum_{k=1}^n x_k \sum_{k=1}^n…
23408924
  • 505
  • 3
  • 14
4
votes
3 answers

Proof by induction: $5^n \geq 5n^3 + 2$ for $n \geq 4$

One of the practice problems I have is to prove by induction that for every $n \geq 4$ the following inequality holds: $5^n \geq 5n^3 + 2$ My progress so far (inequality holds for base case $n=4$): $5^{n+1} \geq 5(5n^3 + 2)$ $5^{n+1} \geq 25n^3 +…
heky__
  • 159
4
votes
2 answers

Infinite intersection of sets, induction

I'm looking for quick clarification on the use of induction, as I'm confused about when it can and can't be applied to claims involving $\infty$. First, the definition of $\bigcap^ \infty_{n=1} A_n$: the set containing all elements that are members…
Redstark
  • 71
4
votes
5 answers

Recursive proof that $n^n \geq n!$

So I'm trying to prove, by induction, that $$ n^n \geq n!, \forall n\geq1$$ Base case: $$ \text{For } n=1, 1^1 = 1 \geq 1 = 1!$$ Hypothesis: $$ n^n \geq n!$$ Step: $$ \text{Trying to prove: } n^{n+1} \geq (n+1)! $$ Now, somewhere around here I get…
Koy
  • 877
  • 1
  • 6
  • 13
4
votes
5 answers

Proof by induction, $1/2 + ... + n/2^n < 2$

So I'm having trouble with proving this homework question by induction. $$ \frac{1}{2^1} + \frac{2}{2^2} + ... +\frac{n-1}{2^{n-1}} + \frac{n}{2^n} <2 $$ I know how to prove that the series converges to 2 (using things like the ratio method), but…
Sammy Aranny
  • 115
4
votes
4 answers

Induction Proof Verification via Binomial Theorem

I am studying from a text with an overview of discrete mathematics in the beginning. The problem in question is to prove by induction that $(1+x)^{k+1}$ $\geq$ $1+nx$ for all naturals, where $x > 1$ I proved this by induction in a similar vein as…
user556576
  • 95
4
votes
1 answer

Prove by induction that $a^{m+n} = a^m \times a^n$ and $(a^m)^n = a^{mn}$, for $a \in \mathbb{R}$ and $n, m \in \mathbb{N}$.

Prove by induction that $a^{m+n} = a^m \times a^n$ and $(a^m)^n = a^{mn}$, for $a \in \mathbb{R}$ and $n, m \in \mathbb{N}$. Using mathematical induction, we should check that for $m, n = 1$, the conclusion is true. Now, what about $k + 1$ and $j +…
Shane Dizzy Sukardy
  • 1,305
1 2 3
…
99 100