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

Induction proof of an identity

I know how to prove this identity using combinatorics. However I want to use induction to prove it now. I know I can use the help of this property: Can you provide a start up/push so that I can continue go on from there?
Sarah cartenz
  • 181
0
votes
3 answers

Prove by induction that $n!+n \geq 2^n$

I'm trying to use the principle of mathematical induction to prove that $n!+n\ge2^n$ for all $n\ge1$. I know how to prove $n!\ge2^n$, but I can't figure out what to do with the extra $n$. For instance, if I try to factor $n+1$ out of the inductive…
Dylan McGuire
  • 3
0
votes
1 answer

Induction proof involving sets

Suppose $A_1,A_2,...A_n$ are sets in some universal set $U$, and $n\geq2$. Prove that $\overline{A_1 \cup A_2 \cup ... \cup A_n}$ = $\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_n}$
Wilson
  • 371
  • 5
  • 17
0
votes
2 answers

Discrete Maths - Induction

I am having difficulty answering the following question: Can anyone show me how to solve this? I understand that I should be putting in a + 1 somewhere to simulate the next step, but I'm not sure where. Thanks!
user3371750
  • 197
0
votes
4 answers

Proving (by induction) the inequality $ \sum_{i=1}^n \frac1{\sqrt i} > 2(\sqrt{n+1}-1), \forall n \in \mathbb N$

Trying to prove that $$ \sum_{i=1}^n \frac1{\sqrt i} > 2(\sqrt{n+1}-1), \forall n \in \mathbb N$$ using induction. My only attempt so far has consisted of squaring both sides (during the $P_{k+1}$ part) to get rid of square roots, but it turned…
Alec
  • 4,094
0
votes
1 answer

I need some quick factoring tips and tricks

Prove that for all $n \in \mathbb N$, $0^2 + 1^2 + 2^2 + \ldots + n^2 = \frac {n(n + 1)(2n + 1)}{6}$. Define $ p(n)=0^2 + 1^2 + 2^2 + \ldots + n^2$. Then: \begin{align*}p(n + 1)&=0^2 + 1^2 + 2^2 + \ldots + n^2 + (n + 1)^2\\ &= \frac {n(n + 1)(2n +…
New Orleans
  • 111
0
votes
2 answers

Induction question - sums

I just proved $\sum_{i=1}^n i^3 = [\frac{n(n+1)}{2}]^2$ using mathematical induction. I have to prove it for $i^4$ now. So would that be $\sum_{i=1}^n i^4 = [\frac{n(n+1)}{2}]^3$ ?
user45417
  • 309
0
votes
2 answers

Proof by induction of a sum.

I am at the step where I am proving $P(k+1)$: $$2^k-1+2^k=2^{k+1}-1$$ How am I going to make these equal? Ps: Just realized this is just an exponent rule, I need coffee.
King Squirrel
  • 2,607
0
votes
1 answer

Prove this binomial sum by induction

Can someone help me with this one? Prove by mathematical induction For $$n\geq1$$ $$\displaystyle{\sum^n_ {k=0} k^n\binom{n}{k}(-1)^k= (-1)^nn!}$$ It's easy to see that for $$n=1$$ $$\displaystyle{0^1\binom{1}{0}(-1)^0+1^1\binom{1}{1}(-1)^1= -1}$$…
Vitor Manuel Ferreira da Silva
  • 1
0
votes
9 answers

Proof by induction: Prove that $6$ divides $9^n - 3^n$

Induction: prove that $6| 9^n - 3^n$, where $n$ is a positive integer inductive step: trying to prove $6| 9^{k+1} - 3^{k+1}$, $= 9^k \cdot 9 - 3^k \cdot 3$ $= 6(\frac3 2 \cdot 9^k - \frac1 2 \cdot 3^k)$ maybe it's not going in a good direction...
Gavin Z.
  • 401
0
votes
2 answers

Prove that for every integer $n \ge 1$, $1 + \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+ ... +\frac{1}{\sqrt{n}}\le 2\sqrt{n}$

I understand that this is an induction question. I start with the base case (n=1): $$1 < 2 \tag{That works!}$$ Induction step: Assume the statement works for all $n = k$, Prove for all $n = k+1$ Assume $1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}}+…
user122661
  • 983
0
votes
3 answers

induction help proving the sum of the n powers of 2

How do i prove using mathematical induction to prove that the sum of the firstn powers of 2 that can be computed by Evaluating function m(n) = $2^n -1$. $\sum_{k=0}^{n-1}2^k=1+2+4+...+2^{n-1} = 2^n-1$ Should i substitute n = 1, k , k+1 in $2^n -1$…
A Good Student
  • 95
0
votes
3 answers

Proof by induction that I'm stumped on.

$$\sum \limits_{k=1}^{n}k(_k^n)=n2^{n-1} $$ I'm trying to solve this by induction but I have no idea where to start and induction was not taught very well so I'm trying to get it cleared up in any way possible.
J0hn
  • 127
0
votes
2 answers

Showing sum of squares of products of all non-empty subsets of $\{1, 2, 3, \ldots, n\}$ having no consecutive elements is $(n + 1)! − 1$

Consider all non-empty subsets of $\{1, 2, \ldots, n\}$ having no consecutive elements. Prove that sum of squares of products of these subsets equals $(n + 1)! − 1$: i.e. if $\mathcal{C}_n$ is the set of all such…
user3078441
  • 147
0
votes
1 answer

Divisibility by induction

I have learnt how to prove expressions by induction based on the use of three assumptions $n=1$, $n=k$, $n=k+1$. But can someone help me prove that $1+10^{2n-1}$ is divisible by $11$
Dr. NGILAZI BANDA
  • 659
1 2 3
…
99 100