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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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
1 answer
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 ...
2 votes
1 answer
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
0 votes
1 answer
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
0 votes
0 answers
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
2 votes
1 answer
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 ...
0 votes
2 answers
51 views

Prove $\arctan(\frac{1}{2})+...+\arctan(\frac{1}{2n^2})=\arctan(\frac{n}{n+1})$ [duplicate]

Base: n=1: $\arctan(\frac{1}{2})=\arctan(\frac{1}{2})$ Suppose for n - true. Need to prove for n+1 $\arctan(\frac{1}{2})+...+\arctan(\frac{1}{2n^2})+\arctan(\frac{1}{2(n+1)^2})=\arctan(\frac{n+1}{n+...
-2 votes
0 answers
54 views

Proof that $\left( 54 \mid 2^{2n+1} - 9n^2 + 3n -2\right)$ for $n\geq 1$

I defined $$S:=\left\{ n\in \mathbb{N}:54\mid \left(2^{2n+1} - 9n^2 + 3n - 2 \right) \land 1\leq n \right\}$$ and want to proof by math induction that $S=U$, where $U:=\left\{ n\in \mathbb{N}: 1 \leq ...
-1 votes
0 answers
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 ...
-3 votes
0 answers
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.
2 votes
0 answers
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
0 votes
1 answer
36 views

Proof by induction $\sum_{i=0}^n i =\frac{(n)(n+1)}{2}$ but instead of using the k + 1 term, using the k -1 term

Complete beginner on the topic, I can say that I lack the formal way of doing this. What I am trying to understand is: During the "inductive step", instead of using $k + 1$ can we assume $k -...
-1 votes
1 answer
60 views

Proof Big O/Combinatorics [closed]

In a combinatorics book, in recursion/induction chapter, there is an exercise that says: Let $f(n)$ be a number sequence such that $f(2n) ≤ 2f(n)+2n$, $f(1) = 0$, $f(2) = 1$. Show that $f(n) ≤ 10^{100}...
2 votes
1 answer
65 views

Show there are $\frac{6^n}{2}$ possible even results from the sum of $n$ dice rolls.

I was requested to show there are $\frac{6^n}{2}$ possible even results from the sum of $n$ dice rolls. I did it via induction and was wondering whether my demonstration is correct. $I$. Let $a_n=\{...
  • 1,914
0 votes
0 answers
23 views

Proof of the basic counting rule (BCR) by induction

I am going through my notes studying for my intro probability course test. I am trying to prove as many theorems as I can from the course notes as this is something we may be tested on, as well I find ...
3 votes
0 answers
31 views

Prove that $a_n = 2^{n+1}-1$ for all whole number $n \ge 0$ [duplicate]

I have the sequence: $$ \begin{cases} a_0=1 \newline a_n = 2a_{n-1}+1, n \ge 1 \end{cases}$$ And I want to prove that $a_n = 2^{n+1}-1$ for all whole number $n \ge 0$ I started by calculating $a_0,...
-1 votes
0 answers
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}$$
-2 votes
2 answers
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
0 votes
2 answers
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
0 votes
0 answers
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
-2 votes
1 answer
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.
user avatar
0 votes
1 answer
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
2 answers
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
2 votes
2 answers
58 views

Prove by induction the inequality $2^{n!}>n^n$ for $n>2$

My attempt so far: Base case: $2^{3!}>3^{3}$ $2^6 > 27$ $64> 27$ Then going for $2^{(n+1)!} > (n+1)^{(n+1)}$ I get $(2^{(n!)})^{(n+1)} > (n+1)^{(n+1)}$ Since n+1 is positive, $2^{n!} &...
3 votes
1 answer
76 views

Using the fact that $\sum_{k=1}^{n}\frac{1}{k}\approx\ln n,$ can two inequalities corresponding to the two main logarithmic identities be proven?

...without using logarithms / exponentials ? The approximation symbol in the title has been used loosely. But from now on I will be more precise. Two of the key properties of logarithms are given by ...
2 votes
0 answers
34 views

Arbitrary variable in induction

I want to prove that for any $a,b\in\mathbb{N}$ that $a+b\in\mathbb{N}$, where $0\in\mathbb{N}$. Here is my attempt with induction: We fix $b$ and induct over $a$. It is true for $a=0,$ since $b+0=b\...
  • 53
0 votes
0 answers
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
1 answer
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 ...
0 votes
1 answer
33 views

Questions about a general term and a number of terms in a finite sum

The inequality below occurs in a proof of convergence of $p$-series for an exponent greater than $1$. Statement: Use induction to show $\displaystyle{1 + \frac{1}{2^r} + \frac{1}{3^r} + \frac{1}{4^r} ...
0 votes
0 answers
35 views

Proof of Inclusion-Exclusion principle without induction

I understand the proof of the principle using induction. But as people argue against induction that guessing the formula in the first place is not so easy, I am trying to prove it without induction. I ...
0 votes
1 answer
43 views

Proving by induction this inequality

I need to prove by induction that $f(n) \geq 2^{n-1}$ when $n$ is a power of $2$, if I know that $f(n) \geq 2 f^2(n/2)$ when $n$ is also a power of $2$. I'm stuck at the inductive step. Let $n = 2^i$ ...
  • 549
5 votes
2 answers
280 views

Proving using Mathematical Induction from my discrete math class [duplicate]

This is a practice exercise from our class about proving inequalities using mathematical induction. I've been stuck on the last step for quite a while now. This is the Question. "Prove that $\...
  • 167
1 vote
0 answers
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
0 votes
2 answers
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
1 answer
42 views

Proving Big-Theta bound

Prove by induction that $$ \frac{n^2}{2} + 3n + \ln(n) \in \Theta (n^2).$$ This my attempt. Base case ($n=1$):$\frac{7}{2} \in \Theta(1)$ is true. Inductive step: Assume $\frac{n^2}{2} + 3n + \ln(n) \...
  • 549
0 votes
2 answers
54 views

Prove the following by induction the following expression

I'm having a hard time trying to solve this problem I get stuck after introducing the induction hypothesis on $p(n+1)$ $p(n)=(n+1)(n+2)(n+3)\dots(n+n)=2^n\cdot1\cdot3\cdot5\dots(2n-1)$ $p(n+1)= (n+1+1)...
0 votes
0 answers
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
0 answers
28 views

Proving using the first principle of mathematical induction

This is an exercise from my Elementary number theory class, it is all about using the first principle of Mathematical Induction for proving. The question goes, Prove that $\sum_{j=1}^n(-1)^{j-1}j^2=1^...
  • 167
3 votes
1 answer
55 views

Let $p(n)$ the predicate $\ln{x}^{n}=n\ln{x}$. Show the implication $p(n)\Rightarrow p(n+1)$ for all natural number $n$.

I need your help with this exercise. I don't know if what I did is correct. Let $p(n)$ the predicate $\ln{x}^{n}=n\ln{x}$. Show the implication $p(n)\Rightarrow p(n+1)$ for all natural number $n$. ...
  • 951
3 votes
2 answers
113 views

Proving using Mathematical Induction

I'm Stuck on the last step, this is proving using mathematical induction, a lecture from my Elementary number theory class. The question goes to, Prove that $\sum_{k=1}^n \frac{1}{k^2}=\frac{1}{1^2}+\...
  • 167
-1 votes
0 answers
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}$ ...
-2 votes
0 answers
29 views

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.
0 votes
1 answer
59 views

$M_{i+1} = M_i - \frac{M_i a_i a_i^T M_i}{a_i^T M_i a_i}$ and $M_1 = I$, find $M_i$ in terms of $(a_1, a_2, ..., a_i)$

Given a sequence of vectors $(a_1, a_2, ...)$ with $(\forall i \in \{ 1, 2, ... \} ) a_i \in \mathbb{R}^n$, we define the following sequence of matrices $(M_1, M_2, ...)$ with $(\forall i \in \{ 1, 2, ...
  • 153
1 vote
2 answers
69 views

Induction extended to ordered pairs: Application of the First Principle of Finite Induction to proving Bertrand’s Ballot Theorem.

In this question, the comments stated the existence of Bertrand’s Ballot Theorem. In reading the article, I found a peculiar application of proof by induction. The text is as follows: We loosen the ...
0 votes
0 answers
59 views

A question about uses of induction in particular problem

Suppose we color a table $2n\times 2n$ with four colors such that, each sub-square $2\times 2$ has $4$ different colors. my question is, could we conclude that top left corner, and top right corner , ...
0 votes
0 answers
24 views

String Reverse Mathematical Induction

Given the following recursive definition of R (string reverse), $ε^R = ε $ $(xa)^R=ax^R$, for a ∈ Σ and x ∈ Σ* prove that $(ax)^R = x^Ra$ using induction HINT: Apply mathematical induction on the ...
0 votes
1 answer
68 views

Prove by in induction

I am new to symbolic logic, and I know the basis of proving by induction. I need help with this question. Consider the function ! : LA → N defined recursively as follows: α! = 0, for any atomic ...
0 votes
0 answers
13 views

prove that each checkpoint belongs to a unique A-chain

I was wondering how to prove that each checkpoint belongs to a unique A-chain in the solution to the problem shown below? I think I might be able to use induction, but I'm not sure what to induct on. ...
  • 515
0 votes
2 answers
38 views

Proof by induction to show that $5^n \geq 4n+1 $ for all natural numbers. [duplicate]

I let my base step be $n=1$, $5^1 \geq 4(1) + 1$ is true. We can now assume that it is true for some number $n = k$ where $k$ is a natural number. We wish to show the claim is still true for $n = k+1$....
0 votes
1 answer
60 views

Ordinary Induction.

Define $S=\left\{ an+b:n\in \mathbb{N}\right\}$, where a and b are integers and $a\neq0$. Write down the statement of ordinary induction on S. What does it mean by "statement of ordinary ...

1
2 3 4 5
191