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

2
votes
2answers
75 views

elementary prove thru induction - dumb stumbling

i am trying to prove this statement for all $n \in \mathbb{N}$ with the help of induction: $4 \sum_{k=1}^{n} (-1)^kk=(-1)^n(2n+1)-1$ base case: n=1 $4 \sum_{k=1}^{1} (-1)^11=-4=(-1)^1(2*1+1)-1$ .. ...
2
votes
3answers
30 views

Induction - Countable Union of Countable Sets

Stephen Abbott has a an exercise in Chapter 1 (1.2.12) that suggests that one cannot use induction to prove that a countable union of countable sets is countably infinite. One answer is that n=...
0
votes
0answers
22 views

Choosing values in a strong induction

The sequence s0,s1,s2... is defined by s0=1 and for all integers n>0, $s(n)=s(⌊n/2⌋)+s(⌊2n/5⌋) + n.$ Prove, using strong induction, that S(n) > 4n for all integers n>=3. To my knowledge, I only have ...
4
votes
0answers
79 views

Are there any proofs that only exist by induction?

I've come to learn more about induction recently for proving things, and one thing stands out to me. It seems like you could just data-mine patterns and guess a relationship you think might be ...
2
votes
6answers
115 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
2
votes
4answers
6k views

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

I'm starting to understand how induction works (with the whole $k \to k+1$ thing), but I'm not exactly sure how summations play a role. I'm a bit confused by this question specifically: $$ \sum_{i=1}^...
1
vote
3answers
44 views

How to prove inequality $3^{n}≤4n!$ for $n≥4$ with mathematical induction?

Prove inequality $3^{n}≤4n!$ for $n≥4$ with mathematical induction. Base step: $n=4$ $3^{4}≤4*4!$ $81≤96$, so statement is true. Inductive step: We need to prove that this $3^{n+1}≤4(n+1)!$ is ...
5
votes
3answers
1k views

Odd Binomial Coefficients?

By Newton's Formula: $$(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k $$ Proof that every $\dbinom{n}{k}$ is odd if and only if $n=2^r-1$. I have already shown that if $n$ is of the form $2^r-1$, ...
8
votes
2answers
138 views

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^{...
1
vote
3answers
80 views

How to prove this inequality $3^{n}\geq n^{2}$ for $n\geq 1$ with mathematical induction?

Prove this inequality $3^{n}\geq n^{2}$ for $n\geq 1$ with mathematical induction. Base step: When $n=1$ $3^{1}\geq1^{2}$, statement is true. Inductive step: We need to prove that this statement $...
0
votes
1answer
74 views

Show that for each positive integer $n$, $a_n$ is a positive integer, $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$ ...
2
votes
2answers
321 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
33 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
88 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
61 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
353 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
53 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
56 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
543 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
92 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 ...
2
votes
6answers
57 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 ...
-1
votes
0answers
44 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
36 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
153 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
125 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
109 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
136 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
59 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
63 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
43 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
121 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
252 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 ...