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
5
votes
6 answers

Proof by Induction Problem

I need to prove that for natural numbers $a$, and positive integers $n$, the number $a^{2n+1}-a$ is divisible by $6$. I have proved the case when $n=1$, that $a^3-a$ is divisible by $6$. I'm having trouble proving that if $a^{2n+1}-a$ is divisible…
Ldog327
  • 519
4
votes
2 answers

Representing Any $n \geq 4$ as a Sum of 2's and 5's

Use induction on $n$ to prove that for all integers $n\geq 4$, postage of $n$ cents can be realized using only $2$ cent and $5$ cent stamps. I thinks it is little bit different. How can I use induction to this kind of problem?
Q123
  • 251
4
votes
2 answers

Proving that if one person in any group of four knows three, then someone knows everyone.

title can't exactly capture the description of this problem so well. Here's the question in full: "At a convention, any group of four people contains one who knows the other three. Prove there is someone at the convention who knows everyone…
user176049
4
votes
2 answers

Can someone please explain the axiom of induction in lay term?

Axiom of Induction To me, it says, for all P such that P(0) AND for all k is an element of natural numbers P(k) implies P(K+1) implies for all n is am element in the natural numbers of P(n) But this is a bit incoherent, can someone please explain…
Olórin
  • 5,415
4
votes
2 answers

using the induction technique to prove $\Pi_{i=1}^{k}(2i-1)=\frac{(2k)!}{(k!)2^k}$

$\Pi_{i=1}^{k}(2i-1)=\frac{(2k)!}{k!2^k}$ clearly the products are in the set of the natural numbers. Step one show that P(1) is true $2(1)-1=1$ True. Step 2 induction assumption $\Pi_{i=1}^{k}(2i-1)=\frac{(2k)!}{k!2^k}$ This is what we assume to…
Fernando Martinez
  • 6,698
  • 19
  • 74
  • 108
4
votes
1 answer

Using $\sqrt{1-t}\leq 1-\frac t2$ to show that $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots2n}\geq\frac1{2\sqrt n}$

I have a problem that tells me to use that $\sqrt{1-t}\leq 1-\frac t2$ for $t\in(0,1)$ to show by induction that $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots2n}\geq\frac1{2\sqrt n}$ So far I have shown that…
Alec
  • 4,094
4
votes
1 answer

Proving that $(a+b+c)^n=a^n + b^n + c^n$

Suppose that $(a+b+c)^3=a^3 + b^3 + c^3$. For what positive integer values of n is it true that $(a+b+c)^n=a^n + b^n + c^n$. Any hint will be much appreciated
user143681
  • 117
4
votes
2 answers

Generating induction proofs from graphs/integrals

I just came across a question on an old take-home exam, Prove, using induction, that $\sum_{k = 1}^{n} \frac{1}{k^2} > \frac{3}{2} - \frac{1}{n} + \frac{1}{2n^2} $ Then I remembered something that the professor said about his method of coming up…
The Chaz 2.0
  • 10,464
4
votes
2 answers

Base cases in strong induction

In strong induction, the inductive hypothesis assumes that for all k, P(k) is true. A lot of the proofs I've come across just take this as an assumption. Why then, in some other cases, is it necessary to provide several base cases instead of just…
Mars
  • 231
  • 1
  • 3
  • 10
4
votes
2 answers

Prove that $x^n+x^{-n} \in \mathbf{N}$ if $x+\frac1x \in \mathbf{N}$

Assume that $x+\frac{1}{x} \in \mathbb{N}$. Prove by induction that $$x^2+\frac1{x^2}, x^3+\frac1{x^3}, \dots , x^n+\frac1{x^n}$$ is also a member of $\mathbb{N}$. I have my base, it is indeed true for $n=1$.. I can assume it is true for…
jacob
  • 2,965
4
votes
1 answer

Cutting a rectangle into squares

A carpenter has a rectangular board, $x$ feet long and $y$ feet wide, with total area $n = xy $square feet. The board is to be divided into n squares (each 1 foot x 1 foot) by successively cutting a rectangle into two smaller rectangles whose sides…
Shorty
  • 467
4
votes
2 answers

Proof by Induction Question with regard to the Knight's Tour

I have to prove that the formula $4n^2-12n+8$ gives the number of edges on a knight graph, where n is the number of vertices horizontally and vertically and n^2 is the number of vertices. I've proved it for $n=4$ (the smallest possible value of $n$…
user101090
4
votes
1 answer

Induction principle

I managed to prove that if $\phi(0)$ and $\forall n(n\in\mathbb{N},\phi(n)\rightarrow\phi(n+1))$ then $\forall n(n\in\mathbb{N}\rightarrow\phi(n))$. The proof is based on the fact that $\{m\in\mathbb{N}:\phi(m)\}$ is an inductive set. Now I'd like…
za4
4
votes
4 answers

Prove for all $m, n \in \mathbb N$: $[1 + 3 +\cdots + (2n -1)]^m = n^{2m}$

I have this: Prove for all $m, n \in \mathbb N$: $$[1 + 3 + \cdots + (2n - 1)]^m = n^{2m}$$ For $n = 1: 1 = 1^2$, hence P(1) is true. Let $N \in \mathbb N$ be given and assume: $$[1 + 3 + \cdots + (2N - 1)]^m = N^{2m}$$ For $n = N + 1$:…
1mvdb
  • 87
  • 4
4
votes
4 answers

Prove that $1^3 + 2^3 + 3^3 +\cdots+ n^3 = \frac14n^4 + \frac12n^3 + \frac14n^2$

I have to prove that this is true using mathematical induction. I have this: for every $n \in \mathbb N$: $1^3 + 2^3 + 3^3 + ... + n^3 = \frac 14n^4 + \frac 12n^3 + \frac 14n^2$ for $n = 1: 1^3 = 1/4 + 1/2 + 1/4$, hence $P(1)$ is true. Let $N \in…
1mvdb
  • 87
  • 4
1 2 3
…
99 100