# 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.

9,540 questions
Filter by
Sorted by
Tagged with
33 views

### Mathematical induction - prove $\sum_{k=1}^n \left(k\cdot k! + \frac k{(k+1)!}\right)= (n + 1)! − \frac1{(n + 1)!}$

Inductive proof of $$\left(1\cdot1! + \frac1{2!}\right) + \left(2\cdot2! + \frac2{3!}\right) + \cdots + \left(n\cdot n! + \frac n{(n+1)!}\right) = (n + 1)! − \frac1{(n + 1)!}$$ for all positive ...
1 vote
46 views

### Why does this fibonacci sequence proof require P(n + 1) for n = 1 be defined explicitly?

I am going through Donald Knuth's The Art of Computer Programming, Vol 1, Chapter 1.2.1: Mathematical Induction. Knuth's inductive strategy (to prove a statement $P(n)$ is true for all positive ...
70 views

### find $\lfloor \prod_{n=2}^{2022} \dfrac{2n+2}{2n+1}\rfloor$

Find $\lfloor \prod_{n=2}^{2022} \dfrac{2n+2}{2n+1}\rfloor$, given that it's coprime to $2022$. I'm not sure if one can telescope the product somehow. There ought to be a way to simplify the product. ...
• 273
36 views

### Prove by induction that $\frac{1}{1 - x} = \sum_{k = 0}^n x ^ k + \frac{x^{n + 1}}{1 - x}$

Prove by induction that $\frac{1}{1 - x} = \sum_{k = 0}^n x ^ k + \frac{x^{n + 1}}{1 - x}$. I'm supposed to prove this is true by induction but am finding it difficult. I already proved it for $n=0$. ...
• 11
24 views

### Structural Induction - bit strings

In this task, we will look at a function that calculates the "cross sum" of a bit string, that is, which returns the number of occurrences of 1 in a bit string. For example, we have that f(...
• 1
53 views

### If $a_1,a_2,\dots,a_n$ are integers and $a_1a_2\cdots a_n=0$ then $a_i=0$ for some $1\le i \le n$

If $a_1,a_2,\dots,a_n$ are integers and $a_1a_2\cdots a_n=0$ then $a_i=0$ for some $1\le i \le n$ I'm trying to prove this by using induction We can prove this for $n=1$ means $a_1=0$ this implies ...
• 2,299
51 views

40 views

### Prove that MergeSort is stable for any input size n ∈ N using induction on n.

In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
49 views

### Prove by induction $2^n \geq n^2-1$ [closed]

base: $2 \geq 0$ Suppose $2^k \geq k^2-1$ is true, want to prove for $k+1$, then: $2 \cdot 2^k\geq k^2+k^2-2$. Don't know what to do next.
78 views
+50

### proof that the truth value that is recursively defined is a function

In first order logic: https://www.cs.ox.ac.uk/people/james.worrell/lecture9-2015.pdf, there is a recursive definition of the truth value of the formulaes: This seems to be a recursive definition, so ...
• 1,200
36 views

65 views

• 31
43 views

### Mathematical Induction Discrete math [duplicate]

Use mathematical induction to prove that the formula is true for all natural numbers $n \geq 1$. $$1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n(n + 1) = \frac{n(n + 1)(n + 2)}{3}$$
47 views

### Fibonacci sequence: Show that $F_{4n-1}$is divisible by 3 [closed]

Show that $F_{4n-1}$ is divisible by 3. I know how to prove the base case of the induction and how to prove what would happen if n is divisible by 3. Nevertheless, I can´t find a path to prove that ...
• 13
50 views

### Show by induction that $n^2 \leq 3^n$ [closed]

In proving $n^2 \leq 3^n$, I have so far got that $3n^2 \leq 3^n \cdot 3$ and I am trying to prove that $(n+1)^2 \leq 3n^2$ to get $(n+1)^2 \leq 3^n \cdot 3$. However, having trouble proving this ...
• 13
32 views

### Proof by induction: every partial order on a finite set can be extended to a linear order

I want to prove that every partial order on a finite set $X$ can be extended to a linear order and I want to do it without assume the axiom of choice. I try to do a proof by induction on the ...
• 125
41 views

### Induction question maybe

Let T be defined as: 0 is in T 1 is in T If 2 elements are in T then their average is in T. Prove that 1/24 is not in T. 34 views

### Proving a formula for the recursive series $w_n=-[w_1+w_2+\cdots +w_{n-1}]+\sqrt{[w_1+w_2+\cdots+w_{n-1}]^2+w_1^2}$ holds for all $n\in \mathbb{Z^+}$.

I have a recursive series within problem I am trying to solve. I need to create a non-recursive formula in terms of $w_1$ and $n$ and prove it works for $n \in \mathbb{Z^+}$. I have found a pattern, ...
1 vote
40 views

### prove that for all $n\ge 1$, $a_n/b_n$ is of the form $a/2^b$ where $a$ is an odd integer and $b < 2n$

For any $n\ge 1,$ let $a_n = 1\cdot 3\cdots (2n-1)$ and let $b_n = 2\cdot 4\cdots (2n)$. Prove that for all $n\ge 1$, $a_n/b_n$ is of the form $a/2^b$ where $a$ is an odd integer and $b < 2n$. I ...
• 515
58 views

• 53
38 views

### Is this a sufficient proof for the recursion theorem

In Paul Halmos "naive set theory" he has a long proof for the recursion theorem. The recursion theorem is If $a$ is an element of a set $X$, and if $f$ is a function from $X$ into $X$, then ...
• 1,200
1 vote
31 views

### Show using induction that $\mathbb{N}^p$ is countable for any $p \in \mathbb{N}$

For $p \in \mathbb{N}$, define $\mathbb{N}^p$:= $\mathbb{N}\times...\times \mathbb{N}$ (p times) to be the set of p-tuples of natural numbers. I'm supposed to prove by induction, but I am not sure how ...
33 views

• 167
1 vote
28 views

### Using number theory for a particular case to achieve strong induction generalisation [duplicate]

So I was looking at a few strong induction problems such as the following "Given an unlimited supply of 5 cent and 7 cent stamps, what postages are possible?" and it seems the computation ...
• 11
79 views

### I dont understand induction on well-orders

Question: (Induction on well-orders) Suppose < is a well-order on A. Suppose $\phi(x)$ is a formula such that for every y $\in A$, if $\phi(x)$ holds for all $x<y$, then $\phi(y)$ holds for all ...
1 vote
42 views

23 views

### Solution in proving using mathematical Induction

This is a part of the proof using mathematical induction, specifically the last step where we prove the inductive step. I saw this solution on the internet, However, I cannot comprehend the solution, ...
• 167
1 vote
28 views

• 167
37 views

### If every small subset of a surjection has an injective-subset, does the big surjection have an injective subset?

Let $\mathcal{A}$ be the set $\begin{Bmatrix}“m”, “a”, “t”, “h”\end{Bmatrix}$ Let $𝒫(\mathcal{A})$ denote the set of all subsets of $\mathcal{A}$. For example, $\begin{Bmatrix} “m”, “t”\end{Bmatrix}$ ...
### Prove that for all $n \geq 2\in \mathbb{Z}$, $f_nf_{n+1} - f_{n-1}f_{n+2} = (-1)^{n+1}$. [duplicate]
I have proved the base cases and am working on proving the $n+1$ case. I have gotten to $(f_{n+1})^{2}-f_nf_{n+2}=(-1)^{n}$. I am unsure how to proceed from here.