Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

1
vote
1answer
32 views

A problem involving induction and upper triangular matrix

Use induction to prove that, if A1, ..., An are upper triangular matrices of the same size, then $\sum_{i=1}^n A_i$ is upper triangular. How do i do this problem? Thank You
1
vote
2answers
27 views

Prove the following infinite trig product by induction.

Prove by induction, that for a positive integrer $n$, that $$\cos x \times \cos2x \times \cos 4x \times \cos 8x ... \times\cos (2^nx) = \frac{\sin(2^{n+1}x)}{2^{n+1}\sin x}$$ So to start I'm gonna ...
0
votes
1answer
26 views

Proof by induction of path composition

Let $w, \alpha_n: I=[0,1] \rightarrow \mathbb{S}^1$, $w(s)=e^{2\pi i s}$, $\alpha_n(s)=e^{2 \pi i n s}$. Let $[u] \in \pi_1(\mathbb{S}^1,1)$ be the path homotopy class of the path $u$, an element of ...
2
votes
1answer
62 views

Proof of a formula to calculate $1^p+2^p+…+n^p$ for arbitrary $n,p\in\mathbb{N}$

$1^p+..+n^p=\sum_{k=1}^{n}k^p$ Suppose I fix an $n$ and set $p=1$ Then one can prove by induction that $1+2+...+n=\frac{1}{2}(n)(n+1)$ Now there is an identity and I am looking for a proof for it ...
-1
votes
1answer
57 views

Prove that \[(x^{2} +xy -y^{2})^{2}=1\] has consecutive Fibonacci numbers as solution [on hold]

Apologies if it's a duplicate question. I was not able to find such question though. I don't know how to proceed on this.
0
votes
1answer
76 views
+50

How to solve this recursion relation?

Suppose: $$2k(n-k)a_k=n(n-1)+(n-k)(k+1)a_{k+1}+(n-k)(k-1)a_{k-1}$$ where $k=1, 2, ..., n-1$ and $a_n=0$, how to derive $a_k$? I tried to find pattern $a_1-a_2=n/2$; $a_2-a3=n(2n-1)/6(n-2)$, it ...
1
vote
1answer
21 views

Mathematical Induction for a defined Fibonacci Function

I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us: $f(0;a,b) = a;$ $f(1;a,b) = b;$ $f(n;a,b)=f(n-1;b, a+b)$ The problem defines ...
1
vote
0answers
22 views

Why restrict to $\Sigma_1^0$ formulas in $RCA_0$ induction?

I'm reading Stillwell's Reverse Mathematics, and the induction axiom was just introduced. For a $\Sigma_1^0$ formula $\phi$, \begin{equation} [\phi(0)\; \wedge\; \forall n\, (\phi(n) \...
-3
votes
2answers
40 views

Inequality Induction with Fractions Help [on hold]

Prove by mathematical induction that for all integers $\ n\geq2 $ $$\ \frac{1}{2}+\frac{2}{3}+...+\frac{n}{n+1}<\frac{n^2}{n+1}$$
0
votes
3answers
28 views

Proof by Induction help (inequality)

I need to prove if, $$a_1=1,\ a_2=2$$ and $$a_n=2a_{n-1}+a_{n-2}$$ then $$a_n\leq \left(\frac{5}{2} \right)^{n-1}$$ Proof (by using strong induction): As far as I go, is that I prove both bases ...
1
vote
0answers
42 views

Induction over HIT (HoTT)

Setting Currently I try to formulate the simply typed $\lambda$-calculus in HoTT which results in quite involved inductive type families. Since I'm still new, I'm often unsure if my induction ...
3
votes
1answer
35 views

Proving the connection between the Binomial Theorem and the product rule for derivatives

Let $a(x)$ and $b(x)$ be smooth functions, i.e they are infinitely times differentiable. I have made the assumption that the derivative for the function $$f(x)= (a\cdot b)(x)$$ can be given by $$...
-1
votes
1answer
49 views

Just want to ask an mathematical induction question which I've tried to solve.. but still cannot get the LHS and RHS.

I have tried to solve this question, but it's kinda tricky here when I form a LHS equation by myself it doesn't equals to the RHS. Can anyone here provide me a step by step guide to proof it? ...
0
votes
1answer
43 views

Proving the determinant for an $n\times n$ matrix equals some value

Let $n \in \mathbb{N}$. For every $1 \leq i, j, \leq n$, let $f_{ij}(x)$ be differentiable. Define the $n \times n$ matrix $A(x)$ whose $(i, j)^{\text{th}}$ entry equals $f_{ij}(x)$. Let $F(x) = \...
0
votes
1answer
55 views

Guess and Prove by induction a formula for the $n$-th element in a sequence $b_n$ [closed]

So I've been given a sequence. The sequence $b_0,b_1,b_2$, ... is defined as follows: $b_0 = 0$, $b_1 = 1/2$, and for integers $n \ge 2$, $b_n = \sqrt{b_{n-1}b_{n-2}} + \frac{3n}{2} - 1.$ My ...
4
votes
2answers
148 views

Proof by induction with sqaure root in denominator: $\frac1{2\sqrt1}+\frac1{3\sqrt2}+\dots+ \frac1{(n+1)\sqrt n} < 2-\frac2{\sqrt{(n+1)}}$

I need to prove $\frac{1}{2\sqrt1} + \frac{1}{3\sqrt2} + ... + \frac{1}{(n+1)\sqrt n} < 2 - \frac{2}{\sqrt{(n+1)}}$ by induction for every $n \in \mathbb{N} $. Please help, I am stuck for 2 days ...
0
votes
2answers
46 views

Guess and prove Formula for Sequence $b_n$ = $\sqrt{b_{n-1}b_{n-2}} + \frac{3n}{2} - 1.$

Having a really hard time wrapping my head around how to approach this. written out the formula up to $b_5$ but not seeing a pattern at all, I've scoured my notes, google and so on. missing some ...
2
votes
1answer
33 views

Proving a statement using induction

Use the principle of Mathematical Induction to show: $$\sum _ { k = 1 } ^ { n } k x ^ { k - 1 } = \frac { 1 - ( n + 1 ) x ^ { n } + n x ^ { n + 1 } } { ( 1 - x ) ^ { 2 } }$$ for every $n\in\mathbb{N}$ ...
3
votes
3answers
180 views

Validity of Using Induction to Show Union of an Infinite Ascending Chain of Subgroups is a Subgroup

Can this be done by induction instead of just proving the subgroup criterion? I can prove using the essentials tools of group theory, but looking at the problem, I was wondering if we can simply use ...
-4
votes
1answer
28 views

Prove the bound exists by induction [closed]

I know that this is true for n=1. How do I proceed after this?
-4
votes
1answer
21 views

Prove by induction that for every nonnegative integer n, 3|((2^(2n)) − 1). [closed]

Rewrite your proof using proof by smallest counterexample. Please explain your answer
1
vote
2answers
31 views

Solving Recurrence Relation Using Substitution/Geometric Series

$$ T(n) =4T(\frac{n}{2})+ n^\frac{5}{2} $$ I'm having trouble solving this recurrence relation above to identify the time complexity below by using substitution/plugging. I'm able to do it using ...
0
votes
1answer
25 views

let P$_n$ be the following statement [duplicate]

let P$_n$ be the following statement: Every group of n persons that contains at least on male contains only males. What is wrong with the following proof by induction that this statement is true for ...
0
votes
0answers
18 views

prove the formula using “complete induction”

$S _ { n } = 2 \cdot S _ { n - 1 } + S _ { n - 2 }$ if $S _ { 1 } = 3$ and $S _ { 2 } = 7$ Prove that for every integer $n \geq 1$ $S _ { n } = \frac { 1 } { 2 } ( 1 + \sqrt { 2 } ) ^ { n + 1 } +...
2
votes
3answers
76 views

Prove $\lim\limits_{n \to \infty} \int_0^1 x^n e^x dx = 0$ by evaluating closed form

While preparing for my numerical analysis exam I encountered the following question Find a recursive definition $I_n = R(I_{n - 1})$ for $I_n := \int_{0}^{1} x^n e^x dx$ and prove $$ I_n = \sum_{...
1
vote
1answer
14 views

Algebraic plateau in proof by induction

Consider the sequence $A_n$$=\frac{81\pi }{2^{2n-2}}, \forall n\in \mathbb{N}$. I'm supposed to prove by induction that the sum of the $n$ first terms of $A_n$ is given by $S_n$$=27\pi \left(4-2^{2-...
1
vote
2answers
43 views

Verify Proof by Mathematical Induction: $n^2 > 4n+1$

I am just learning proof by mathematical induction and wanted to verify if I got the following proof right Use induction to prove $n^2 > 4n + 1$ Proceed with induction. For $n = 5$. The left ...
4
votes
2answers
534 views

Applying the induction hypothesis indirectly? I have trouble understanding this proof.

I am confused about the mechanics of the following proof (page 423, chapter 20, of the fourth edition of Spivak's Calculus (Taylor's Theorem)): I am not sure that I understand how applying the ...
1
vote
1answer
30 views

Invariant for Gale–Shapley algorithm (Mating Ritual Algorithm)?

I found the following invariant for Mating Ritual algorithm (Lehman, Leighton and Meyer, Mathematics for Computer Science, §6.4) while going through MIT reading material: Definition. Let $P$ be the ...
0
votes
0answers
39 views

Proof by Induction of a recurrence relation

I am stuck with following proof which I am not able to get. One such code is a list of $2n$ $n$-bit strings in which each string (except the first) differs from the previous one in exactly one bit. ...
0
votes
2answers
43 views

Prove that any integer amount of currency greater than 17 cents can always be formed. [duplicate]

In a strange country, there are only 4 cent and 7 cent coins. Prove that any integer amount of currency greater than 17 cents can always be formed. Do I use induction to show this? ...
-1
votes
0answers
35 views

Show that the determinant of an upper triangular matrix equals the product of its diagonal

I need to prove this statment by mathematical induction over $n$. Let $R = (r_{ij})_{ij} \in K^{n \times n} \,$ be an upper triangular matrix. Then apply $\det(R)=\prod\limits_{k=1}^{n}~r_{kk}$. Can ...
1
vote
1answer
30 views

How to prove that a recursive formula always reaches a threshold by induction

I have a recursive formula: $f(n) = \frac{f(n-1)+1}{2} $ where $f(0) = h$ I should prove inductively that for any real h, f(n) will always eventually cross a threshold 1, meaning that f(n) will ...
1
vote
2answers
75 views

Prove by induction: $C(2n, 2) = 2C(n, 2) + n^2$

Show that if $n$ is a positive integer, then $C(2n, 2) = 2C(n, 2) + n^2$. Here, $C(a, b)$ means the binomial coefficient $\dbinom{a}{b}$. Prove this by induction. Here is my calculation: $n$ ...
0
votes
1answer
63 views

Prove that $\sum_{i=1}^n \frac{1}{\sqrt i} < 2 \sqrt n$ by induction - result doesn't match to wolfram alpha's result

According to wolfram alpha, this inequality isn't true for $n > 2$. My result says otherwise. Assuming that the inequality is true for $n+1$, $\sum_{i=1}^{n+1} \frac{1}{\sqrt i} < 2 \sqrt {n+1}...
1
vote
1answer
47 views

How can I prove the following matrix equality?

Let $n\in\mathbb{N}$ be arbitrary. Why is the following equality true? $$ \left(\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix} + 3 \begin{pmatrix}4 & 6\\-2 & -3\end{pmatrix}\right)^n = \...
0
votes
0answers
37 views

Soccer Tournament Statement to Symbolic Forms

Suppose there is a tournament involving $b$ teams where $b \ge 2$. It is viable to name the teams as $T_1, T_2, \cdots T_b$ so that $T_r$ beats $T_{r+1}$ for any $r$ from $1$ to $b-1$. Here is what I'...
3
votes
1answer
59 views

Proof by induction: $3^n|a_n\ $

$$Problem$$ Given $ (a_n)_{n\in N}$ the sequence defined by: $$a_1=15,\ a_2=18,\ a_{n+2}=6a_{n+1}-7a_n^4,\ \forall n\in \mathbb{N}$$ Prove by induction that $\forall n \in N$ a) $3^n|a_n$ b) $3^{...
1
vote
4answers
56 views

Prove by induction that $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$ for all integers $n \ge 2$

Having trouble with the concept of proving an inequality. Q: Prove by induction that $\sum_{i=1}^n \frac{1}{\sqrt i} > \sqrt n$ for all integers $n \ge 2$ Here is what I have so far: Basis ($n=2$...
0
votes
3answers
39 views

How to prove $a_1 = 2$, $a_2 = 4$ and $a_{n+1} = \frac{1}{3}(2a_n+a_{n-1})$ for all $n \geq2$

Let $a_1 = 3$, $a_2 = 4$ and $a_{n+1} = \frac{1}{3}(2a_n+a_{n-1})$ for all $n \geq2$ Prove that for all positive integers $n$, $3 \leq a_n \leq4$ This was a practice problem in my textbook in the ...
1
vote
2answers
40 views

Prove that $\sum_{i=1}^{n} i \times i! = (n+1)! - 1$ by induction

\begin{align*} \sum_{i = 1}^{k + 1} i(i!) & = \sum_{i = 1}^{k} i(i!) + (k + 1)(k + 1)!\\ & = (k + 1)! - 1 + (k + 1)(k + 1)! & \text{by the induction hypothesis}\\...
1
vote
1answer
45 views

Proving that every natural number can be expressed as the sum of distinct Fibonacci numbers

The Fibonacci sequence $f_1, f_2, f_3, \ldots$ is defined by $f_1 = 1, f_2 = 2$, and $f_m = f_{m−1} + f_{m−2}$ for each integer $m \ge 3$. Prove that every $n \in \mathbb{N}$ can be expressed as the ...
-1
votes
2answers
47 views

For every n ∈ N, prove that $(1 − 1/2 )(1 − 1/2^2 ). . .(1 − 1/2^n ) ≥ 1/4 + 1/2^{n+1}$ through induction.

this is a homework question for my university math proofs. I've spent over an hour and cannot figure it out. For this induction proof I understand the base case but can't seem to solve the inductive ...
0
votes
1answer
47 views

Swapping elements to form a specific permutation - Formal Proof

Considering a permutation of [1, 2, ..., n], it is fairly obvious that on doing n/2 swaps we arrive at the permutation [n, n-1, ..., 1]. This can be achieved by swapping the first element with the ...
17
votes
5answers
1k views

Are we properly using mathematical induction?

I recently had a lecture in a Computer Science course involving the use of induction. The main discrepancy lies in that a few students and I think our proof should suffice, but our instructor argues ...
0
votes
2answers
34 views

Need help finishing proving this summation inequality by induction

I'm having a hard time solving the following problem: Prove by induction that $\forall\ n\in\mathbb{N} $: $$\sum_{i=1}^{n} \frac{n+i}{i+1}\ge n$$ I checked the base case, and then made it up to ...
1
vote
2answers
30 views

Is this application of induction correct?

Prove that the sum of first $n$ natural numbers is $\frac{n(n+1)}{2}$ So I verify the base case for $n=1$. Now I assume that the proposition is true for all natural numbers up to $n=k$. So my ...
3
votes
4answers
60 views

How to solve $\frac{1}{1*2} + \frac{1}{2*3} + \frac{1}{3*4} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}$ [duplicate]

I am stuck on factoring out everything properly. I feel like I am combining these fractions wrong or something because I always have an extra 1. edit: edit: I am still stuck. Math isn't working out, ...
1
vote
1answer
21 views

Need help with logs in proof by induction

Show that $a + ar + ar^2 + \dots + ar^n = \frac{a(a-r^{n+1})}{1-r}$ for $a = 1, r = 5$ $a)~~n = 1$ $$1 + 5 = \frac{1(1-5^2)}{1-5} = \frac{-24}{-4}$$ $$6 = 6$$ $b)~~n = k+1$ $$1 + 5 + 5^2 + \...
-2
votes
1answer
39 views

Show that $1^3+2^3+…+n^3=(1+2+3+…+n)^2$ [duplicate]

Block quote I use induction N=1 And n=k But in case of n=k+1 i can't write the thing .help Block quote