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

Prove by induction that $36,306,3006,30006$ is divisible by 18

Hi I'm quite new to induction so I don't really know how I should tackle this problem. I took out a calculator and checked the results 2,16,167,1667 I sort of see a pattern but how would I start the induction?
J.Hao
  • 13
  • 1
0
votes
1 answer

Prove the arithmetic-geometric inequality for integers $n$ that are powers of two, i.e. $n=2^k$.

Prove the AG inequality for integers $n$ that are powers of two, i.e. $n=2^k$. Suppose $a_1,a_2,\dots,a_n>0$. The arithmetic mean of these numbers is $$\frac{a_1+\dots+a_n}{n}.$$ The geometric mean is $$ \sqrt{a_1\cdot \dots \cdot a_n}.$$ The…
Username Unknown
  • 4,633
0
votes
3 answers

Prove that $6^{n+1} + 4$ is divisible by 4

I hope you can understand me, English isn't my main language. I have a superior algebra problem that I can't solve. Prove that for every n in Natural numbers ($N$) $$6^{n+1} + 4$$ is divisible by 4 I'm really lost about this problem. -First I…
Arturo
  • 3
0
votes
3 answers

Prove by induction that $\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m}, \qquad \forall n \in N$

Prove by mathematical inductin that: $$\sum_{k=n+1}^{2n} \frac{1}{k} = \sum_{m=1}^{2n} \frac{(-1)^{m+1}}{m}, \qquad \forall n \in N$$ is true. For $n=1$, ($\frac{1}{2} = \frac{1}{2})$ it holds. But what to do more? Can you give me a hint? I tried…
Gjekaks
  • 1,133
0
votes
1 answer

prove by induction that $F(n) \leq \left(\frac{1 + \sqrt{5}}{2}\right)^n$

I had the following prove by induction problem in an exam and I didn't do it because I didn't know how to. Could anyone solve it, please? $F(0) = 0$ $F(1) = 1$ $F(n) = F(n-1) - F(n-2)$ $F(n) \leq (\frac{1+\sqrt{5}}{2})^n$ Thank you
zeeks
  • 241
0
votes
1 answer

Proof by induction: Number of subsets of cardinality $2$ of set with $n$ elements is $\frac{n(n-1)}{2}$

We would like to prove by induction that the number of subsets of cardinality $2$ of a finite set with $n$ elements is given by $\frac{n(n-1)}{2}$. I know the reason why this is true, but how could I use it in the induction process? Something seems…
nullgeppetto
  • 3,006
0
votes
1 answer

Find LHS for Induction : Total number of triples selected from N items = N(N-1)(N-2)/6

How do I find the LHS for finding the total number of sets of k items each selected from N items. Order does not matter. For e.g. 1+2+3+...+n = n(n+1)/2 How do I find the LHS for my query? RHS is n(n-1)(n-2)/6 and the question is "Show that total…
Chandan Pednekar
  • 103
0
votes
1 answer

Discrete Mathematics Proving Question

I need help with this proof. I am stuck on this question and don't know how to do it: Prove that: $$ \forall n \in \mathbb{N}, \sum\limits_{i=2}^{2^n} \frac{1}{i} \geq \frac{n}{2}$$
Johnny
  • 1
0
votes
2 answers

Explain a statement about math induction base.

I was reading an article in wikipedia about math induction: http://en.wikipedia.org/wiki/Mathematical_induction And there is a sentence: "Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers." It is…
user9943
0
votes
3 answers

Proof that $x_{n+1} = 1+\frac{2}{x_n}$ is monotonally decreasing for all $n = 2k$

$x_1 = 1$ $x_{n+1} = 1+ \frac{2}{x_n}$ It's obviously true for $x_2$ and $x_4$, but I'm missing where and how to use the induction hypothesis to prove that $x_{2(k+1)} = x_{2k+2} \leq x_{2k+4} = x_{2(k+1+1)}$
Clayton Louden
  • 155
0
votes
1 answer

Mathematical Induction Questions Summation and Inequality

For all three questions use the principle of mathematical induction to show that for all integers $n≥3$ $(1-\frac23)(1-\frac23)(1-\frac23)+...+(1-\frac2n)= \frac2{n(n+1)}$ $2*1!+5*2!+10*3!+...+(n^2+1)n! = n(n+1)!$ For all integers $n≥2$…
Wilson Huynh
  • 73
0
votes
4 answers

inductive step confusion in sum of all positive integers example

I am confused with the inductive step of this very basic induction example in the book Discrete Mathematics and Its Applications: $$1 + 2+· · ·+k = k(k + 1) / 2$$ When we apply $k+1$, the equation becomes: $$1 + 2+· · ·+k+(k+1) = k+1(k + 1)+ 1 / 2 =…
lightning_missile
  • 491
0
votes
1 answer

Base case not the same for two equivalent forms of the statement

Prove that the following statement holds for all natural numbers: $$1\cdot2\cdot2^{n} + 2\cdot3\cdot2^{n-1} + \dots +n\cdot(n+1)\cdot2+(n+1)\cdot(n+2) = 2^{n+4}-(n^2-7n+14)$$ I don't need help with the whole proof, just with the base step I somehow…
0lt
  • 657
0
votes
2 answers

Prove by induction: $\frac{2^{2n}}{n+1}<\frac{(2n)!}{(n!)^2},n>1$

Prove by induction: $\frac{2^{2n}}{n+1}<\frac{(2n)!}{(n!)^2},n>1$ For $n=2$ equality holds. For $n=k$ $$\frac{2^{2k}}{k+1}<\frac{(2k)!}{(k!)^2}$$ For $n=k+1$ $$\frac{2^{2k+2}}{k+2}<\frac{(2k+2)!}{((k+1)!)^2}$$ How to prove this?
user300045
  • 3,449
0
votes
1 answer

Recursive/Strong Induction

Suppose that $a_0, a_1, a_2, \dots$ is a sequence defined as follows. $$a_0 = 2, a_1 = 4, a_2 = 6 \text{, and } a_k = 7 a_{k-3} \text{ for all integers $k \ge 3$.}$$ Prove that $a_n$ is even for all integers $n \ge 0$.
isharailanga
  • 115
1 2 3
…
99 100