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

Induction Proof and divisibility by $2^n$

I'm trying to use induction to prove that for every integer $n > 0$ there exists an $n$-digit integer A(n) that is divisible by $2^n$ and that consists entirely of digits “1” and “2”. Does anyone have a clue where to start ? I found examples that…
BrainOverfl0w
  • 197
  • 8
6
votes
3 answers

Mathematical Induction and "the product of odd numbers is odd"

I am extremely poor at proofs and logical manipulation so I am stuck on a lot of these questions especially induction. The question below I have been stuck at for a little over 1 hour and I can't get it, I have tried various substitutions and forms…
Raynos
  • 1,623
6
votes
3 answers

Prove by induction $T(n) = 2T(\frac{n}{2}) + 2$

I'm stuck with this induction proof: So far, given: $\begin{align*} T(1) & = 2 \\ T(n) & = 2T(n/2)+2 \\ & = 2(2T(n/[2^2])+2) + 2 \\ & = [2^2]T(n/[2^2]) + [2^2] + 2 \\ & = [2^2](2T(n/[2^2])+2) + [2^2] + 2 \\ & = [2^3]T(n/[2^3]) + [2^3] + [2^2] + 2…
Irwin
  • 203
6
votes
5 answers

prove by induction $7 \mid 3^{3^n}+8$

Okay so ive been trying to prove this for about 5 hours... really need salvation from the geniouses around here. prove by induction $7\mid 3^{3^n}+8$ i really need some directions on what to do here...
Tal
  • 315
6
votes
3 answers

How do I prove that any chessboard of size $n \times 3$, where n is even and $n \geq 10$, has a closed knight's tour?

I'm currently stuck on a problem from my computer theory class homework. The question asks me to prove, using induction, that any chessboard of size $n \times 3$, where $n$ is even and $\geq 10$, will have a closed knight's tour. I've worked on the…
John D.
  • 61
6
votes
3 answers

Use induction: prove any postal charge of $\geq$ 12 cents can be formed by 4 and 5-cent stamps

I'm reading from my book about mathematical induction, and there is an example that says "Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps" let P(n) be the statement that postage of n cents can…
FrostyStraw
  • 1,045
6
votes
2 answers

How do you prove $n! \leq (n/2) ^n$?

I'd be really grateful if someone could help me figure out how you prove $n!\leq (n/2) ^n$ ?
user104389
6
votes
3 answers

Can an inductive proof with a fixed parameter assume the hypothesis proved for a different value of that parameter?

Suppose we are trying to prove a statement $\forall n\forall k\varphi(n,k)$. We fix $n$ and proceed to prove $\forall k\varphi(n,k)$ by induction. We show the base case $k=0$, we suppose it's true for $k-1$, but then when showing the inductive step…
IllogicalUser
  • 437
6
votes
1 answer

Prove $\sum_{i=1}^{n}i^3=\frac{1}{4} n^2(n+1)^2$ (induction)

Problem Prove $$\sum_{i=1}^{n}i^3=\frac{1}{4} n^2(n+1)^2$$ Attempt to solve I would try to prove this with induction. We have sum and the sum as function of $p(n)$. Now i try to prove that the sum equals $p(n)$ with induction.…
Tuki
  • 2,237
6
votes
1 answer

Prove the sequence is perfect square

Question Given a sequence $a_0 = a_1 = 97\sqrt{2}$ and $$\forall n \space \space a_{n+1}= \frac{1}{\sqrt{2}}[a_n a_{n-1} + \sqrt{(a_n^2-2)(a_{n-1}^2-2)}]$$ Proof that $$2+\sqrt{2+a_n\sqrt{2}}$$ is a perfect square My approach Use mathematical…
Clark Makmur
  • 537
6
votes
2 answers

Understanding the Definition of Well-Founded Induction

I would like to understand how to apply well-founded induction. I have found two definitions which I list now, followed by the question. (1) A binary relation $\prec$ is well-founded if there are no infinite descending chains. An infinite…
Lance
  • 3,698
6
votes
3 answers

Mathematical Induction: $3^n +1$ is even for all values of positive integers

I am not sure how to go about this "proof by induction" problem. below is my attempt. Base Case: $n = 0$,substituting the value of $n$ to the equation $3^n+1$ $$= 3^0 + 1$$ $$= 1 + 1 = 2 $$ Thus the equation holds true for initial value of $n$ i.e…
Smit
  • 239
6
votes
3 answers

Can we use mathematical induction when induction basis is 'too' broad?

Imagine I wanted to use the induction principle to prove that a certain proposition was true for diagonal matrices. The induction is done in the dimension of the matrix. So, the induction basis is for $n=1$. However, at this basis, there is no…
An old man in the sea.
  • 5,241
6
votes
4 answers

demonstration by induction: $(1+a)^n ≥1+an$

Demonstrate by induction: $(1+a)^n ≥1+an$ is true, given a real number $a$, for any $n ∈ \mathbb N$. With $a > 0$ I need to demostre this using the induction principle. My doubt is in the second part of the demonstration. This is what I have: In…
Nerian
  • 321
6
votes
4 answers

Induction proof: $S$ contains powers of 2 and predecessors implies $S={\bf N}$

Let $S$ be a subset of $\mathbb{N}$ such that $$2^k\in S\quad\forall\ k\in\mathbb N$$ and, $$k\in S\Rightarrow k-1\in S\quad\forall\ k\ge2,k\in\mathbb N$$ Show by induction that $S=\mathbb N$.
Spenser
  • 19,469
1 2
3
…
99 100