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

learn more… | top users | synonyms

8
votes
2answers
100 views
+50

How to prove by induction that $3^{3n}+1$ is divisible by $3^n+1$ for $(n=1,2,…)$

So this is what I've tried: Checked the statement for $n=1$ - it's valid. Assume that $3^{3n}+1=k(3^n+1)$ where $k$ is a whole number (for some n). Proving for $n+1$: $$3^{3n+3}+1=3^33^{3n}+1=3^3(3^{...
2
votes
2answers
319 views

Solving Induction $\prod\limits_{i=1}^{n-1}\left(1+\frac{1}{i}\right)^{i} = \frac{n^{n}}{n!}$

I try to solve this by induction: $$ \prod_{i=1}^{n-1}\left(1+\frac{1}{i} \right)^{i} = \frac{n^{n}}{n!} $$ This leads me to: $$ \prod_{i=1}^{n+1-1}\left(1+\frac{1}{i}\right)^{i} = \frac{(n+1)^{n+1}}...
1
vote
1answer
28 views

Difference between set theory proof and logic proof of complete induction

Set theory proof: Let $\mathbf{A}$ be the set such that $\{0,1,2,...,n\} \subset \mathbf{A} \implies n+1 \in \mathbf{A}$. Our goal is to show that $\mathbf{A} = \mathbb{N}$. To do this, we construct ...
0
votes
6answers
80 views

How to prove if this $\sum_{l=0}^{n}\binom{n}{l}=2^{n}$ is valid for all $n\in \mathbb{N}$? [duplicate]

Prove for for all $n\in \mathbb{N}$: $\sum_{l=0}^{n}\binom{n}{l}=2^{n}$ I know the steps of induction but i have no idea how to prove this equation with binomial coefficient. 1) For the induction ...
1
vote
3answers
58 views

Mathematical Induction Inequality problem [on hold]

I am trying to solve the following problem with mathematical induction: $$ \forall n>1,\qquad \frac{1}{2^2}+\frac{1}{3^2}+\ldots+\frac{1}{n^2}<\frac{n-1}{n} $$ but since I am new to the concept ...
1
vote
2answers
352 views

Proving the geometric sum formula by induction

$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$ I want to prove this by induction. Here's what I have. $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$ I wanted to factor a $q^{...
1
vote
1answer
24 views

Need help with inductive proof of Binomial Theorem

I'm new to math and trying to learn about the Binomial Theorem, by following this tutorial. I got stuck trying to read the Induction Proof. They give an example of using the Sum notation: $$ (x + y)^...
2
votes
3answers
50 views

Proof related to Harmonic Progression

The question is as follows: Let $m_1<m_2<m_3<\cdots<m_k$ be postive integers such that $\frac{1}{m_1}$, $\frac{1}{m_2}$, $\frac{1}{m_3}$, $\cdots$, $\frac{1}{m_k}$ are in arithmetic ...
1
vote
0answers
55 views

Induction Method in a special case of $ n!+1 = m^2 $ (Brocard's Problem)

Context: Brocard's problem is a problem in mathematics that asks to find integer values of $n$ and $m$ for which$$ n!+1 = m^2 \tag{1}$$ Let's define, $$T=\left(\left\lfloor \frac{ (\lfloor\log(n) \...
10
votes
8answers
539 views

Proving $\sum_{k=1}^n k k!=(n+1)!-1$

Prove: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferably combinatorially) It's pretty easy to think of a story for the RHS: arrange $n+1$ people in a row and remove the the option of everyone ...
-1
votes
4answers
91 views

Prove $n^{n/2} < n!$ if $n \gt 2$ [duplicate]

Ive been stuck on this question for so long.How do i do it? $n^{n/2} < n!$ if $n \gt 2, n \in \mathbb{N}$. Please help guys.
1
vote
0answers
15 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
1
vote
6answers
56 views

Prove by induction that $a^{4n+1}-a$ is divisible by 30 for any a and $n\ge1$

It is valid for n=1, and if I assume that $a^{4n+1}-a=30k$ for some n and continue from there with $a^{4n+5}-a=30k=>a^4a^{4n+1}-a$ then I try to write this in the form of $a^4(a^{4n+1}-a)-X$ so I ...
0
votes
5answers
53 views

How do I prove that for $\forall n\in \mathbb{N}$ $\sum_{k=1}^{n}k(k+1)=\frac{1}{3}n(n+1)(n+2)$?

How do I prove that for $\forall n\in \mathbb{N}$ $\sum_{k=1}^{n}k(k+1)=\frac{1}{3}n(n+1)(n+2)$? I need to use induction. For example if n=1. Than 2=2. If statement holds for $\forall n\in \...
48
votes
16answers
4k views

How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction?

Using mathematical induction, I have proved that $$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$ for every integer $n > 0$. I would like to know if there is another way of proving this result ...
0
votes
0answers
40 views

How does the induction proof work in this solution?

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, http://math.stackexchange.com/a/928412, we need 3 steps for that proof. ...
0
votes
1answer
35 views

Prove that $\sum_{i=1}^{n^2} \left \lfloor \sqrt{i} \right \rfloor = \frac{n(4n^2 - 3n + 5)}{6} $ using induction?

Clearly, it's true for n=1. Assuming true for n=k, we have $$\left \lfloor \sqrt{1} \right \rfloor + \left \lfloor \sqrt{2} \right \rfloor ..... + k = \frac{k(4k^2 - 3k + 5)}{6} $$ But how can we ...
0
votes
3answers
35 views

Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the ...
1
vote
2answers
162 views

Proving a combinatorics equality: $\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}$

How to prove the following? Should I use induction or something else? Let $n$ and $r$ be positive integers with $n \ge r$. Prove that $$\binom{r}{r} + \binom{r+1}{r} + \cdots + \binom{n}{r} = \...
0
votes
2answers
35 views

Clarification on inductive proof of Bernoulli's inequality

Prove that if $h > -1$, then $1 + nh ≤ (1+h^n)$ for all nonnegative integers $n$. I've read several solutions and I'm still totally lost on how to go about this. I have the inductive hypothesis:...
3
votes
2answers
151 views

Inequality and Induction: $\prod_{i=1}^n\frac{2i-1}{2i}$ $<$ $\frac{1}{\sqrt{2n+1}}$ [duplicate]

I needed to prove that $\prod_{i=1}^n\frac{2i-1}{2i}$ $<$ $\frac{1}{\sqrt{2n+1}}$, $\forall n \geq 1$ . I've atempted by induction. I proved the case for $n=1$ and assumed it holds ...
1
vote
2answers
152 views

Mathematics induction on inequality: $2^n \ge 3n^2 +5$ for $n\ge8$

I want to prove $2^n \ge 3n^2 +5$--call this statement $S(n)$--for $n\ge8$ Basis step with $n = 8$, which $\text{LHS} \ge \text{RHS}$, and $S(8)$ is true. Then I proceed to inductive step by ...
1
vote
7answers
124 views

Induction and convergence of an inequality: $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots(2n)}\leq \frac{1}{\sqrt{2n+1}}$

Problem statement: Prove that $\frac{1*3*5*...*(2n-1)}{2*4*6*...(2n)}\leq \frac{1}{\sqrt{2n+1}}$ and that there exists a limit when $n \to \infty $. , $n\in \mathbb{N}$ My progress LHS is ...
1
vote
3answers
107 views

Proof of an inequality by induction: $(1 + x_1)(1 + x_2)…(1 + x_n) \ge 1 + x_1 + x_2 + … + x_n$

Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + ...
2
votes
3answers
53 views

Proof by induction: inequality $n! > n^3$ for $n > 5$

I'm given a inequality as such: $n! > n^3$ Where n > 5, I've done this so far: BC: n = 6, 6! > 720 (Works) IH: let n = k, we have that: $k! > k^3$ IS: try n = k+1, (I'm told to only work ...
4
votes
4answers
135 views

Prove by mathematical induction that: $\forall n \in \mathbb{N}: 3^{n} > n^{3}$

Prove by mathematical induction that: $$\forall n \in \mathbb{N}: 3^{n} > n^{3}$$ Step 1: Show that the statement is true for $n = 1$: $$3^{1} > 1^{3} \Rightarrow 3 > 1$$ Step 2: Show ...
-2
votes
3answers
86 views

Prove the inequality by induction: $3^n > n^3$ for $n\ge4$ [duplicate]

Prove the inequality by induction: $3^n > n^3\ $ for $\ n \geq 4$ Edit: 1) Base case: $n=4$, $3^4>4^3, 81>64$ 2) Assume true for n=k: so $3^k>k^3$ 3) Consider $(k+1)^3$, $(k+1)^3 = k^...
1
vote
2answers
108 views

Proof by induction; inequality $1\cdot3+2\cdot4+3\cdot5+\dots+n(n+2) \ge \frac{n^3+5n}3$

Ok so I'm kind of struggling with this: The question is: "Use mathematical induction to prove that 1*3 + 2*4 + 3*5 + ··· + n(n + 2) ≥ (1/3)(n^3 + 5n) for n≥1" Okay, so P(1) is true as 1(1+2)=3 and (...
1
vote
2answers
120 views

Trying to prove $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ and use this to prove… [duplicate]

I am trying to prove this $2( \sqrt{n+1}-\sqrt n )< \frac{1}{\sqrt n}<2( \sqrt{n}-\sqrt {n-1})$ if $n \ge 1$ and using this to prove $2\sqrt{m}-2<\sum^m_{n=1} \frac{1}{\sqrt n}<2( 2\sqrt{m}...
1
vote
3answers
58 views

Proving $ \bigcup_{i=1}^n A_{i} \text{ is finite.} $ by Induction.

Prove : If $A_{1},A_{2},...,A_{n} \text{ are finite sets, then } $$$ \bigcup_{i=1}^n A_{i} \text{ is finite.} $$ Proof: (I) Basis Step : $p(1)$ is true because it is true because it is finite. ...
1
vote
2answers
78 views

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

Suppose that $x\ne 1$ and $n\in\mathbb{N}^*$. Prove with induction that $$\sum_{k=0}^{n-1}x^{k}=\frac{x^n-1}{x-1}$$ It seems simple but I have tried for I don't know how long by now... Anyone can ...
0
votes
0answers
36 views

D. F. Wallace's “Everything and more” $\S$7b : Cantor transfinite derivation from $P^{(n)}$

On $\S$7b of David Foster Wallace's book "Everything and more", the author explains how Cantor derived the concept of transfinite numbers from P, a second-species infinite point-set. "$P'$, can be "...
0
votes
2answers
62 views

How can I prove $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ is divisible by $10$ for any odd $n$?

Assuming this is true: $1^n+2^n+3^n+4^n$ divisible by $10$ for any odd $n$ ($n$ is natural) How can I prove that for $n+2$: $1^{n+2} + 2^{n+2} + 3^{n+2} + 4^{n+2}$ Is divisible by 10 as well ? ...
1
vote
0answers
42 views

Proving $a^ma^n=a^{m+n}$ by induction when $n$ or $m$ is negative (or both)

Suppose we have already proved this exponent law for when $m,n\in\mathbb{Z^+}$ as in here. Also suppose $x^{-n}=\frac{1}{x^n}$ is given as a definition. Let $m=-\lambda$ and $n=-\gamma$, where $\...
1
vote
5answers
116 views

Proving that $4k < 2^k$ by induction [duplicate]

Prove that $4k < 2^k$ by induction. It holds for $k = 5$. Assume $ k = n + 1 $. Then $4(n+1) < 2^{(n+1)}$ $4n + 4 < 2^n * 2$ $2n + 2 \leq 2^n$ Now I just need to show that $2n + 2 \leq ...
3
votes
3answers
228 views

Non-induction proof of $2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1$

Prove that $$2\sqrt{n+1}-2<\sum_{k=1}^{n}{\frac{1}{\sqrt{k}}}<2\sqrt{n}-1.$$ After playing around with the sum, I couldn't get anywhere so I proved inequalities by induction. I'm however ...
6
votes
3answers
250 views

Proof of inequality $2(\sqrt{n+1}-\sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n} - \sqrt{n-1})$ using induction

Prove that $2(\sqrt{n+1}-\sqrt{n}) < \frac{1}{\sqrt{n}} < 2(\sqrt{n} - \sqrt{n-1})$ if $n \ge 1$ using induction. Can someone help me with this problem please. Base case is easily shown, and ...
0
votes
6answers
1k views

Prove that $\log(x) < x$ for $x > 0$, $x\in \mathbb{N}$.

I'm trying to prove $ \log(x) < x$ for $x > 0$ by induction. Base case: $x = 1$ $\log (1) < 1$ ---> $0 < 1$ which is certainly true. Inductive hypothesis: Assume $x = k$ ---> $\log(k) ...
1
vote
3answers
70 views

Prove by induction that $\det(A^T) = \det (A)$ [closed]

If $A$ is an $n\times n$ matrix then $\det(A^T) = det(A) $. Prove by induction that the matrix obtained by deleting the $i^{\rm th}$ row and $j^{\rm th}$ column of $A^T$ is the transpose of the ...
9
votes
4answers
138 views

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

Prove via induction that $\sum_{i=1}^n \frac{i}{(i+1)!}=1- \frac{1}{(n+1)!}$ Having a very difficult time with this proof, have done pages of work but I keep ending up with 1/(k+2). Not sure when to ...
0
votes
1answer
57 views

Prove $\sum_{i=1}^{n}\frac{i}{(i+1)!}= 1-\frac1{(n+1)!}$ [duplicate]

Required to prove: $1-\frac1{(k+2)!}$ $$\begin{align*} \sum_{i=1}^{k+1}\frac{i}{(i+1)!}&=\sum_{i=1}^k\frac{i}{(i+1)!}+\frac{k+1}{(k+2)!}\\ &= 1-\frac1{(k+1)!}+\frac{k+1}{(k+2)!}\tag{induction ...
0
votes
1answer
22 views

How does $af\left(\frac{n}{b}\right) \leq cf(n)$ imply that $a^{i}f\left(\frac{n}{b^{i}}\right) \leq c^{i}f(n)$?

This is part of a proof for the third case in the Master Theorem in [CLRS], 3rd edition. $a\geq 1$, $b>1$ and $c<1$. Also, $f$ is a nonnegative function. It makes sense for polynomial ...
5
votes
3answers
88 views

Factorial Proof by Induction Question? [duplicate]

$\text{Use the PMI to prove the following for all natural numbers n.}$ $ \frac{1}{2!} + \frac{2}{3!} + \cdot \cdot \cdot + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!} $ So for this question I get ...
3
votes
2answers
2k views

Show that $e^x > 1 + x + x^2/2! + \cdots + x^k/k!$ for $n \geq 0$, $x > 0$ by induction

Show that if $n \geq 0$ and $x>0$, then $$ e^x > 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}.$$ Not sure where to get started with this induction proof.
1
vote
1answer
63 views

Prove that $ \text{len}(q^*) \le 3\text{len}(q) -2 $

Prove by induction where q is a formula in proposition logic: $$ \text{len}(q^*) \le 3\text{len}(q) -2 $$ Where the star property (*) is defined as follows: $$ \text{atom}^* = \text{atom} $$ $$ (\...
3
votes
5answers
90 views

Use the PMI to prove the following $4^{k}-1$ is divisible by 3.

$4^{n}-1$ is divisible by $3.$ (i) Basis Step: $P(1)$is true because $4^1 -1=3 $ and $3\mid3$. (ii) Suppose $P(k)$ is true for induction hypothesis $3\mid4^{k}-1$. Show $(k+1)$ is true $3\mid4^{k+...
0
votes
1answer
67 views

$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$

Let $a$ be a positive integer and $\{a_n\}$ be defined by $a_0 = 0$ and $$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$$ Show that for each positive integer $n$, $a_n$ ...
33
votes
10answers
10k views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
1
vote
5answers
70 views

Proving that $1\cdot 2+2\cdot 3+\cdots+n\left( n+1 \right) =\frac { n\left( n+1 \right) \left( n+2 \right) }{ 3 } $ by induction

Prove that $$1\cdot 2+2\cdot 3+\cdots+n\left( n+1 \right) =\frac { n\left( n+1 \right) \left( n+2 \right) }{ 3 }. $$ I can get to $1/3(k+1)(k+2) + (k+1)(k+2)$ but then finishing off and ...
0
votes
1answer
577 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...