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

Counting Induction Proof

Consider the set of bitstrings $x\in\{0,1\}^{n+k}$ with $n$ zeros and $k$ ones with the additional condition that no ones are adjacent. (For $n=3$ and $k=2$, for example, the legal bitstrings are $00101$, $01001$, $01010$, $10001$, $10010$, and…
ccptmkvamiokzyoclp
  • 33
0
votes
3 answers

Mathematical Induction (power of four exceeds multiple of three by one)

The Question: Prove by mathematical induction that $4^k - 1$ is divisible by $3$. $p = (4^k-1) \bmod 3 = 0$. The Answer: If $k = 1$, $(4^k - 1) \bmod 3 = 0$, which is true. Assuming $4^k - 1$ is true, lets continue to the induction…
Ishmael
  • 297
0
votes
1 answer

Strong Induction Questions

Are there any proofs that cannot be done using mathematical induction, but can be done using strong induction? Is the proof of every integer≥2 is divisible by a prime? Appreciate the help!
spuddy
  • 186
0
votes
1 answer

Get the intuition behind proof by induction

Any proof which is proven by direct proof method is easy to understand and feel. How do you get the feel or intuition behind the proof when a theorem or lemma is proved using the principle of mathematical induction?
akr_
  • 131
0
votes
2 answers

Double induction with a constraint

If I want to do a mathematical double induction on $n$ and $t$ where $n \in \mathbb{N}$ and $1 \leqslant t \leqslant n$ then obviously the base step is $P(n=1,t=1)$ but how do I implement the induction hypothesis. Im very confused as I can’t assume…
Partey5
  • 1,280
0
votes
1 answer

Show that if $x_1, x_2, ..., x_n > 0$ and $x_1 \cdot x_2 \cdot ... \cdot x_n = 1$ then $x_1 + x_2 + ... x_n \ge n$

I have to show that $\forall n \in \mathbb{N}, n \ge 2$ if we have $$x_1, x_2, ... x_n > 0$$ and $$x_1 \cdot x_2 \cdot ... \cdot x_n = 1$$ then it is true that $$x_1 + x_2 + ... x_n \ge n$$ How can I prove this? The textbook recommends using…
user592938
0
votes
2 answers

Proof by induction that $n! > n^3$ where $n>5$

I have to prove by induction that $n! > n^3.$ This how far I've reached: Induction Hypothesis: $k! > k^3$. Induction step: Basically for Inductive step, I have to show that, $(k+1)! > (k+1)^3$. L.S = $(k+1)! = k!(k+1)$ Where do I go from here? Any…
Muttaki
  • 1
0
votes
5 answers

Divisibility using induction

Want to show $$17^{2k} + 42^k + 93^{2k+1}$$ is divisible by 19 for every natural number k. I started with induction and showed base case when $$k =1$$ Then the induction hypothesis : Let this be true$$19 | 17^{2k} + 42^k + 93^{2k+1}$$ Induction…
user737542
0
votes
3 answers

$7^n + 2\cdot 4^n$ is divisible by $3$ (Proof by induction)

Can someone please help? I'm stuck with this question. I've currently got if $P(k)$ is true then $7^k +2 \cdot 4^k = 3A$ for all $n \in \mathbb Z^+$ Now $7^{k+1} + 2 \cdot (4^{k+1}) = 7 \cdot 7^k + 2 \cdot 4\cdot4^k$
Taylor
  • 1
  • 2
0
votes
0 answers

Complete Induction $n\ge2$ is equal to a product of prime numbers.

Prove by complete induction that any natural number $n\ge2$ is equal to a product of prime numbers.
none
  • 9
  • 2
0
votes
2 answers

Prove $\frac{n(n+1)}{2}$ by induction, triangular numbers

Prove that the $n$-th triangular number is: $$T_n = \dfrac{n(n+1)}{2}$$ I did this: Base case: $\frac{1(1+1)}{2}=1$, which is true. Then I assumed that $T_k=\frac{k(k+1)}{2}$ is true. $$T_{k+1} = \frac{(k+1)(k+1+1)}{2}$$ I'm not sure what to do…
Segmentation fault
  • 1,765
0
votes
1 answer

Show that the sequence $(an)_{n \in \mathbb N}$ is increasing using induction.

The sequence $(a_n)_{n \in \mathbb N}$ is defined recursively as follows: $$ \left\{ \begin{split} a_1=&1 \\ a_{n+1}=&\sqrt{a_n+2} \end{split} \right. $$ a) Prove the sequence $(a_n)_{n \in \mathbb N}$ is increasing (using induction) b) Show…
fraser92
  • 5
0
votes
2 answers

How do I pick a basis case in proof by induction when the start of the range is unclear?

Proof by induction requires a basis case which is a starting value in a sequence such as n=0. Assume we're proving a theorem which doesn't have a clear basis case. It can be any value from -infinity to +infinity. Which value is chosen for the basis…
user148298
  • 121
0
votes
1 answer

Using induction to prove a formula

Suppose $~a_0 = 1~$ and $~a_n = 2a_{n−1} + 3~$ for all $~n ≥ 1$. Using proof by induction, prove that the formula for an for all $~n ≥ 0~$ is given by $~a_n = 2^{n+2} − 3$. How can I solve this question?
Rishika
  • 3
0
votes
0 answers

Question about semantics regarding induction

I’ve noticed it’s conventional in most literature to state the base case as a lower bound in an inductive hypothesis. So for example if the base case is P(1) then in the inductive hypothesis P(k) it’s usually stated that k is a positive integer…
Angela
  • 89
1 2 3
…
99 100