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,773
questions
0
votes
0
answers
36
views
How to prove $1^3+5^3+3^3=153,16^3+50^3+33^3=165033,166^3+500^3+333^3=166500333,\cdots$ with mathematical induction?
$1^3+5^3+3^3=153$
$16^3+50^3+33^3=165033$
$166^3+500^3+333^3=166500333$
$1666^3+5000^3+3333^3=166650003333$
$...$
People in the below link proves the above identities.
The proof without mathematical ...
- 11
0
votes
0
answers
37
views
Can one prove a continuous inequality by "induction"? [duplicate]
I want to prove an inequality of the following form: $$f(x) \le g(x) \quad \forall x \ge 0.$$
In my case, $f(0) = g(0)$
I am wondering if the following would be a viable method. Is the inequality ...
- 3
0
votes
0
answers
49
views
Prove using induction over the positive integers
Prove using induction that the sum of the first step $n$ positive even integers is $n(n+1)$. In other words, prove using induction that $2 + 4 + 6 + … + 2n = n(n+1)$.
So, for my base case I have: the ...
-2
votes
3
answers
66
views
Prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$ [duplicate]
How to prove $(n+1)^{m+1}-(-n)^{m+1}$ is divisible by $2n+1$, with $n,m$ positive integers?
I have tried by induction (on $n$) and with the binomial theorem, something like this (have also assumed $m$ ...
- 9
2
votes
0
answers
35
views
What does it mean that we need $𝜖_0$ induction to prove PA consistency?
I have started to learn about Peano Arithmetic, and also about ordinals.
In particular, I have seen that the Goodstein theorem is an example of a statement that can be expressed in PA but that ...
- 389
0
votes
1
answer
35
views
Proving finite composition of functions using mathematical induction
Let $f:\mathbb{R}\to\mathbb{R}$ be a Baire one function. I need to prove $f^n$ is Baire one for $n=1,2,\dots,k$ by using $\epsilon-\delta$ characterization of Baire one functions:
A function $f:\...
- 365
1
vote
0
answers
29
views
General Solution to Secular Terms in ODE System: Inductive Proof
Attached is a proof of the general solution to a system of differential equations that has secular terms as a result of repeated eigenvalues, and hence solved using a Jordan Normal form.
I can follow ...
- 364
1
vote
0
answers
40
views
Proving $ {1 \over 2\sqrt1} + {1 \over 3\sqrt2} + \dots + {1 \over (n+1)\sqrt n} \lt 2$ using induction [duplicate]
I have come across this problem when practicing induction. As stated in the title, it is required to prove $$ {1 \over 2\sqrt1} + {1 \over 3\sqrt2} + \dots + {1 \over (n+1)\sqrt n} \lt 2~~~ \forall n \...
- 11
-1
votes
0
answers
50
views
Prove $(2n+1)+(2n+3)+\ldots+(4n+1)=3n^2+4n+1$ with induction [closed]
Prove $(2n+1)+(2n+3)+\ldots+(4n+1)=3n^2+4n+1$ with induction.
Can you please explain how to solve this? I don't get how even to start this solution.
I don't even know what the base step is.
What does ...
- 11
0
votes
2
answers
20
views
Breaking the implication chain in inductive reasoning
This is a question from An Invitation to Combinatorics. The question is as follow:
A specific statement about the positive integer n is denoted by P(n). We can ...
0
votes
1
answer
108
views
If $x$ and $y$ are numbers such that $x + y, x^2 + y^2, x^3 + y^3$ and $x^4 + y^4$ are all integers. Show that $x^n + y^n$ is an integer.
If $x$ and $y$ are numbers such that $x + y, x^2 + y^2, x^3 + y^3$ and $x^4 + y^4$ are all integers. Show that $x^n + y^n$ is an integer for all positive integers $n$.
Using induction we have the ...
- 75
2
votes
4
answers
1k
views
Peano axiom of induction with "no junk"
In this Wikipedia treatment of Peano Axioms, if you go down to the first picture you'll see a circle of dominoes and a straight line of dominoes:
The caption says the straight line of dominoes
The ...
- 850
1
vote
1
answer
60
views
A (Faulty) Proof that $(-1)^{n}$ is Monotone
A weird non-proof involving induction that I stumbled upon during my Real Analysis homework. Neither me or my professor could find what was wrong with it.
Theorem: Define the sequence $a_n$ as a ...
- 37
-1
votes
0
answers
18
views
Proving Contrapositive oin proof by Induction [duplicate]
In Inductive step in proof by induction we assume that P(n) is true and show that P(n+1) is true, that is proving the implication (P(n) -> P(n+1)).
My question is can I prove the contrapositive of ...
1
vote
1
answer
31
views
Symmetric difference of a set and its n-th preimage
I have a question about the following statement:
Let $X$ be a set and $f:X\to X$ a map, then for any subset $A\subset X$ and all $n\in\mathbb{N}$
$$A\triangle f^{-n}(A)\subseteq\bigcup_{i=0}^{n-1}f^{-...
- 11
5
votes
3
answers
100
views
Proving the sum of length of a unique path in a tree is less than equal to $n$ choose $2$.
I am having trouble on trying to prove this statement using induction. Given a tree with $n$ vertices with $n \geq 2$. $x$ is a fixed vertex, for each $v$ in the vertex set, $d(v,x)$ is the length of ...
- 81
-3
votes
0
answers
87
views
How can I use the proof by induction in this inequality? [closed]
I have been trying to prove the inequality $$(2n)! \geq 2n(n-1)^2\cdot 4^{n-1}$$ for all positive integers $n$, but I'm unsure how to proceed with the inductive step when using mathematical induction.
...
2
votes
1
answer
78
views
Proof Verification: $2^n+1 \leq 3^n$
Claim: $$\forall n \in \mathbb{N}, 2^n+1 \leq 3^n $$
Proof (Induction): Base: Let $$n = 1, 2^1 + 1 \leq 3$$so this is true. Inductive Step: Suppose $$n \geq 1$$ and assume inductive hypothesis holds ...
- 33
0
votes
2
answers
64
views
How do I complete this proof by induction?
Prove by induction that $u_n>\frac{1}{2}$ $∀n∈\mathbb{N}$ ; given $u_{n+1}=\frac{u_n^2+1}{u_n+2}$ and $u_1=1$.
(Where $\mathbb{N}=${$1,2,3,...$})
Let $P_n$ be the statement to be proved.
The base ...
- 15
4
votes
3
answers
85
views
Prove that any positive integer can be written as sum of distinct numbers from $1,2,3,4,5,10,20,\ldots$
The sequence $1,2,3,4,5,10,20,40,\ldots$ starts as an arithmetic series, but after the first five terms, it becomes a geometric series. The problem is to prove by induction that any positive integer ...
- 579
0
votes
0
answers
32
views
Subset Inequality Problem
Here’s a problem I have been looking at recently. I’m looking for feedback, references, and/or solutions. Thanks. FGS 3.13.23.
Given
A set $X$ of $6$ natural numbers $X = \{X_1, X_2, X_3, X_4, ...
- 1
-3
votes
1
answer
46
views
An exercise from Shapiro's Abstract Algebra [duplicate]
Ex. 8 of the first chapter. The statement is as follows.
This exercise is higly recommended if you want or need to practice induction proofs. We define $a^2$ as $a*a$, $a^3$ as $a*a*a$, and for $n $ a ...
- 573
1
vote
0
answers
38
views
Prove that exists Gray Codes of length $\lceil \log_2 k \rceil$ for any positive integer $k$
Prove that exists Gray Codes of length $\lceil \log_2 k \rceil$ for
any positive integer $k$. The Gray codes for even $k$ values are
closed (form a unique cycle), the ones for odd $k$ values are open.
...
0
votes
2
answers
53
views
Stuck on mathematical induction proof at inductive step [duplicate]
Here's the problem: Use induction to prove: For every integer $n\geq 1$, the number $n^5 − n$ is a multiple of 5.
This is what I have so far:
Basis: $ n= 1$, $n^5-n = 1-1 = 0 = (5)(0)$ so $1^5 - 1$ is ...
- 59
0
votes
2
answers
82
views
Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$
Let $p,q\in\mathbb N$.
Prove with induction on $q$: $\forall p\in\mathbb N\hspace{1em}\left(\frac{p}{q}\right)^{2}\neq2$.
Things I already proved and might help:
$p^2\neq2$
if $(\frac{p}{q})^2=2$ ...
- 25
0
votes
6
answers
861
views
Existential crisis about proof by induction
I recently read this post on this website and it gave me a bit of an existential crisis about proof by induction. My understanding is that, in proof by induction, we show two things to be true: $P(0)$ ...
- 25
-1
votes
1
answer
74
views
Prove the product of 3 consecutive positive integers is always divisible by 6 via induction [duplicate]
There is a problem asking me to prove the product of 3 consecutive integers is always divisible by 6 by using induction and not using the fact that one of the 3 numbers must always be divisible by 3.
...
4
votes
2
answers
72
views
Confusion in a proof that there is no $n$ such that $1<n<2$?
I am trying to follow a proof in Hijab's: Introduction to Calculus and Analysis.
He gives the definition of inductive set:
And then there is this proof where he shows that there is no $n$ between $1$ ...
- 23.1k
3
votes
0
answers
91
views
Inequality for triple product of Stirling numbers
Let ${n\brace k}$ be the Strirling number of the second kind, such that ${n+1\brace k} =k{n\brace k}+{n\brace k-1}$ with ${0\brace 0}=1$. Let $j,p,n$ integers such that $1 \le j \le p \le n$.
I ...
- 3,611
2
votes
2
answers
71
views
Is my proof by mathematical induction that $n(n+2)$ is divisble by 4 correct?
Problem:
Prove that $n(n+2)$ is divisible by $4$ by using mathematical induction, if $n$ is any even positive integer.
My attempt:
$P(q):$ "$2q(2q+2)$ is divisible by $4$", where $q$ is a ...
- 2,923
1
vote
0
answers
62
views
Prove using mathematical induction that $1 \cdot 2 + 2\cdot3+ ...+n(n+1) = \frac{n(n+1)(n+2)}{3}$ [duplicate]
I need to prove that for any n ∈ $\mathbb{N}$, $\begin{equation}\label{eqn1}1 \cdot 2 + 2\cdot3+ ...+n(n+1) = \frac{n(n+1)(n+2)}{3}\end{equation}$ (1). So, this is what I've done so far:
BASIS STEP: ...
- 53
0
votes
2
answers
72
views
Equivalent inductive step to $P(n) \implies P(n+1)$
In a usual proof by induction the inductive step involves assuming $P(n)$ is true and then showing that $P(n+1)$ follows.
Are there any other valid inductive steps? That is, can we define an ...
- 77
1
vote
4
answers
67
views
Proof that $3 \mid 10^{n+2} - 2*10^n + 7, \forall n \in \mathbb{Z}^+$.
This is what I have so far.
Proof by Induction. Let $n \in \mathbb{Z}^+$ Let $P(n)$ be the statement that $10^{n+2} - 2*10^n + 7$ is divisible by 3.
($\textit{Base Case}$): Let $n = 1$.
$$
10^{1+2} - ...
- 102
1
vote
0
answers
71
views
Finding area of a rectangle divided into smaller rectangles
A rectangle is divided into $mn$ smaller rectangles, whose sides are parallel with the big rectangle. Procedure is as follows: you can point to an arbitrary smaller rectangle (rectangle which contains ...
- 11
1
vote
2
answers
57
views
Proof by induction of inequality. For $n \geq 2, 3^n \gt 2^n+n^2$
I'm trying to understand proof by induction on inequalities.
One problem I have is:
Prove that for $n \geq 2$ $3^n \gt 2^n+n^2$
I can prove the base case as $n=2$:
$3^2 \gt 2^2+2^2$
$9 \gt 8$
...
- 31
2
votes
1
answer
52
views
Apostol calculus volume 1, exercise 1.7 question 1b clarification. How can area of infinite points be zero
Question 1 of the exercise asks us to:
“Prove that each of the following sets is measurable and has zero area using the axioms of area in the foregoing section”
Part b of the question is to do so for ...
0
votes
1
answer
76
views
Circularity on Unique Readability for Terms [closed]
I have begun self-studying Logic (I am a numerical physicist), and I am stuck at the very beginning. I have a problem with the proof of the Unique Readability Theorem for Terms in First Order Logic (...
- 1
2
votes
1
answer
44
views
Why can we rewrite $x^{k + 1} - y^{k + 1}$ as $x^{k + 1} - x^ky - y^{k + 1}$ in math induction?
In an exercise, I had to prove by induction that $(x^n-y^n)$ is divisible by $(x-y)$ for all $n\in\mathbb{N}$. But I don't understand one of the algebraic manipulation, and to give you more context, ...
0
votes
0
answers
84
views
How do I use induction for inequalities? [duplicate]
$2^n$ < $(n+1)!$
I'm not too familiar with how to do questions structured like these, as the examples I find online seem to randomly add things into the inequality to make is correct. The farthest ...
- 79
0
votes
3
answers
25
views
Finding the sum of products of digits of all k-digit integers [closed]
My brain is kinda fried, so I'm having trouble finding the pattern that I should use to represent this question generally.
If p(n) represents the product of all digits in the decimal representation of ...
- 53
0
votes
0
answers
43
views
Equivalence of Two Kinds of Induction
Principle Of Finite Induction (PFI)- If $S\subseteq\mathbb{N}$ is a set such that the following conditions are satisfied-
$1.\textrm{ }1\in S,$ and
$2.\textrm{ }k\in S\implies k+1\in S,$
then, $S=\...
- 631
0
votes
0
answers
22
views
Proving the generalized mediant inequality by using induction
Given:
$\frac{a_{1}}{b_{1}}$ $\le$ $\frac{a_{2}}{b_{2}}$ $\le$ ... $\le$ $\frac{a_{n}}{b_{n}}$
with all ${b_{i}}$ being positive
Proof by using induction that:
$\frac{a_{1}}{b_{1}}$ $\le$ $\frac{a_{1} ...
- 1
0
votes
1
answer
65
views
Find the explicit formula for this recurrence relation [closed]
Solve this recurrence relation:
$$a_0 = 1$$
$$a_n = 2^{2(5-n)+1}* a_{n-1} + 1$$
We've only covered linear homogeneous recurrence relation in our course so I'm a little lost and any help would be ...
- 29
3
votes
2
answers
432
views
Mathematical induction proof for integers
Use mathematical induction to prove that $n! > 4^n$ for $n \geq 9$.
My attempt:
Base case: For $n=9$, we have $9! = 362880$ and $4^9 = 262144$
Since $9! > 4^9$, the statement is true for $n=9$
...
- 137
0
votes
0
answers
87
views
Prove the recurrence relation $T(n) = 2T(n/2) + n$ is equal to $n\log(n) + n$ using induction
Question
Given the recurrence relation for the Merge Sort algorithm:
$T(n) = 1$, if $n = 1$
$T(n) = 2T(n/2) + n$, if $n > 1$
Prove by induction that $T(n) = n\log(n) + n$ and hence $O(n\log(n))$
My ...
0
votes
1
answer
54
views
On a rather strange induction [duplicate]
I've been studying elementary number theory for a while now, and when it's possible, to wit somewhat elegant, I love using induction.
I was solving the following problem: "if m$\phi$(m) = n$\phi$(...
- 7
7
votes
2
answers
157
views
Given $a_1$, find an increasing sequence so that $a_1+\dots+a_k $ divides $ a_1^2+\dots+a_k^2$ for all $k$
Prove that for every natural number $a_1>1$ there's an infinite series $a_1<a_2<a_3<...$ such that for every natural number $k,$ $a_1+a_2+...+a_k \vert a_1^2+a_2^2+...+a_k^2$.
At first ...
- 417
1
vote
1
answer
69
views
Matrix Proof Inverses
Can someone help me prove this please?
Suppose that $A_1,A_2,....A_m$ are all invertible $n \times n$ matrices. Then, $(A_1\cdot A_2,....\cdot A_m)^{-1}=A_1^{-1}\cdot.....\cdot A_{m-1}^{-1}\cdot A_{m}^...
- 953
0
votes
1
answer
54
views
Prove inequality by induction: $\sum _{i=1}^n\frac{1}{\sqrt{i}} > 2\left(\sqrt{n+1}-1\right)$ for $n \ge 1$
I worked through most of this problem but am getting stuck on the final bit.
Base: $n = 1$: $\frac{1}{\sqrt{1}} > 2(\sqrt{2}-1)\to\sqrt{9}> \sqrt{8}$. through moving stuff around
Hypothesis: ...
-1
votes
1
answer
44
views
Prove by induction that every integer n, n>=0 can be represented by 5a+7b for a, b in Z [duplicate]
I feel that I could solve this question normally, especially given the closely-related question on this site, but I'm having trouble approaching it by induction.
I assume that 5a + 7b = n is true, ...