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
7answers
83 views

How do you prove that $4^n > n^3$ for all positive integers $n$?

Prove that $4^n > n^3$ for every positive integer $n$ using the Principle of Mathematical Induction. I am well aware of how to use this proof technique. I first showed that P(1) is true: $4^1 ...
0
votes
1answer
26 views

Prove $x^n$ + x < ($x^n$)x using PMI

I need to prove $x^n$ + x < $x^n\cdot$ x, n $\in$ N, x $\in$ R>2 using induction. I started by $x^n$ + x + (x^(n+1)+x) < ($x^n\cdot$ x) + (x^(n+1)+x) I simplified to this: < 2x^(n+1) ...
0
votes
2answers
75 views

INMO Problem with even function proof. [duplicate]

Let $n$ be a natural number. Show that $$\left[ \frac{n}{1} \right ] + \left[ \frac{n}{2} \right ] + \left[ \frac{n}{3} \right ] + \cdots + \left[ \frac{n}{n} \right ] + [\sqrt{n}]$$ is even. ...
1
vote
0answers
32 views

Exercise in induction (including double indices)

The following is for an exam preparation exercise in induction Problem: Let $f(x)=|x| = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$ and $g(x)=|x|^{2k+1}$. Let $N \leq n$ and let $k \in \mathbb{Z}$, ...
2
votes
1answer
50 views

What proof is there that all numbers behave as the numbers we commonly use?

This is a question from someone who is very new to math, so please excuse my ignorance. In a couple of places, I have learned proof by induction, which claims to prove for a set of all integers. A ...
0
votes
0answers
15 views

Monotonicity of n-th root by induction

Suppose a,b are real numbers. I'm trying to prove that $\forall n\geq 1$ ( $0<a<b$ entails $0 <a^{1/n}<b^{1/n}$ ) with the method of Induction. P.S : I already know how to ...
2
votes
1answer
72 views

Fifth root of an even number

Assume $x>1$ is an even integer, show that. $$\sqrt[5]{x} \notin \mathbb{N}$$ I am not sure if this is actually a true theorem, I am conjecturing based on $2, 4, 6, 8, 10, .... 126$. I am ...
3
votes
0answers
35 views

Induction proof - not sure how to proceed with next step

Define two sequences $A_n, B_n$ as follows: \begin{align*} A_1 &= 1\\ A_2 &= 3\\ A_3 &= 2 \cdot 3+1=7 \\ A_4 &= 2 \cdot 7 + 3 = 17\\ A_5 &= 2 \cdot 17 + 7 = 41\\ A_n &= ...
0
votes
1answer
12 views

finite intersection of a family of sets same as countable intersection?

I am reading definition of semi-algebra and one of its properties is that it is closed under finite intersection. In that case can't it be proved that it is also closed under countably infinite ...
29
votes
4answers
2k views

Avoiding proof by induction

Proofs that proceed by induction are almost always unsatisfying to me. They do not seem to deepen understanding, I would describe something that is true by induction as being "true by a technicality". ...
3
votes
3answers
60 views

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI.

For all integers $n \ge 1$, prove 6 divides $n(n+1)(n+2)$ by PMI. I check for my base case, it holds. Then, my inductive hypothesis that for any arbitrary $n \ge 1$, 6 divides $n(n+1)(n+2)$ so ...
0
votes
1answer
63 views

Induction step of a power of 2 with ceiling function

I have to prove the following excercise: "Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integersto the set of ...
0
votes
1answer
102 views

Proving some property of a Formal Logic Language [duplicate]

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq ...
1
vote
1answer
34 views

How can I fix this proof using transfinite induction of the existence of bases of normed vector spaces?

I want to prove that every normed vector space has a basis. The following proof relies on the principle of transfinite induction. I believe that it is flawed because I'm not so sure if it's possible ...
7
votes
7answers
135 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
vote
5answers
36 views

Proving $n! < n^n$ by induction for all $n\geq 2$.

I am having trouble simplifying an induction question. The question is: Let $P(n)$ be the statement that $n! < n^n$ where $n$ is an integer greater than $1$. My work so far: Base case $n = 2$ ...
1
vote
1answer
39 views

Explaining setup of the inductive step in a Fibonacci proof exercise

I have the following exercise to be proved by mathematical induction and also I have the answer about how to solve it: $$ f(0) - f(1) + f(2) - \ldots - f(2n-1) + f(2n) = f(2n-1) - 1 $$ where ...
1
vote
1answer
32 views

Show by induction: $ \frac{a_{2n+4}}{a_{n+2}}=\frac{a_{2n+2}}{a_{n+1}}+\frac{a_{2n}}{a_{n}}$

I would appreciate if somebody could help me with the following problem: Q: Sequence $\{a_n\}$; satisfy $a_{n+2}=a_{n+1}+a_{n}, a_1=1,a_2=1$ Show by induction: $$ ...
2
votes
3answers
55 views

Show $P(1), P(2),…,P(99)$ true statements but $P(100)$ is false.

Provide a sequence of statements, $P(n),$ for $n\in \mathbb{N}$ such that $P(1), P(2),...,P(99)$ are all true but $P(100)$ is a false statement. My try: Let $n\in \mathbb{N}$ and let $0\notin ...
2
votes
1answer
50 views

Prove or disprove $n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n \geq 2 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( 1 - \frac{1}{i^2} \right ) ~=~ \frac{n+1}{2n} $$ And i am not ...
0
votes
1answer
29 views

prove or disprove $n > 0 ~\rightarrow~\prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ \frac{1}{(2n~+~2)!}$

I am working on one of my HW assignments $$ \forall n \in \mathbb{Z}, ~ n > 0 ~\rightarrow~ \prod \limits_{i=1}^{n} \left ( \frac{1}{2i~+~1} \cdot \frac{1}{2i~+~2} \right ) ~=~ ...
1
vote
2answers
20 views

Suppose a matrix A is nxn, and that v1,v2 are in R^n…

Sorry, this is my first time posting here, so if my question is worded incorrectly, please let me know. Anyway, I'm studying for an exam coming up, and this is one of the questions that I'm trying to ...
0
votes
2answers
40 views

mathematical induction to establish inequality

Studying for a test in discrete mathematics and I cannot seem to grasp the explanations in the textbook regarding these questions. Using mathematical induction, prove that $$2^n > n^2, \text{for ...
38
votes
9answers
1k views

Fake induction proofs

Question: Can you provide an example of a claim where the base case holds but there is a subtle flaw in the inductive step that leads to a fake proof of a clearly erroneous result? [Note: Please do ...
2
votes
1answer
38 views

Help with how to prepare the inductive step of a strong induction exercise.

I have the following exercise: "Use strong induction to prove that $f_1^2 + f_2^2 + \cdots + f_n^2 = (f_n)(f_{n+1})$ where $f_n$ in the nth Fibonacci number." This is what I have done: Fibonacci ...
0
votes
4answers
93 views

I'm having trouble with induction. Prove $1 + 2^3 + 3^3 + … + n^3 = \frac{((n^2)(n+1)^2)}4$ [duplicate]

I started a new course and I'm expected to know this stuff, and I'm having trouble learning some on my own. I'm stuck with this problem: Prove $1 + 2^3 + 3^3 + ... + n^3 = \frac{((n^2)(n+1)^2)}4$ ...
1
vote
1answer
40 views

prove that if m and n are any positive integers and m is odd, then $ m \mid \sum \limits_{i=0}^{m-1} (n ~+~ i)$ is divisible by m.

Trying to figure out the induction prof on this theorem: $$ \forall m,n \in \mathbb{Z}, ~ m,n \geq 1 ~\land~ m \equiv 1(\mod 2) ~\rightarrow~ m \mid \sum \limits_{i=0}^{m-1} (n ~+~ i) $$ I got the ...
2
votes
2answers
107 views

Why General Leibniz rule and Newton's Binomial are so similar?

The binomial expansion: $$(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$$ The General Leibniz rule (used as a generalization of the product rule for derivatives): $$(fg)^{(n)} = ...
3
votes
1answer
77 views

Proving $\sum_{i=0}^n 2^i=2^{n+1}-1$ by induction.

Firstly, this is a homework problem so please do not just give an answer away. Hints and suggestions are really all I'm looking for. I must prove the following using mathematical induction: For ...
5
votes
3answers
73 views

Proving $2(\sqrt{n} - 1) < \sum\limits_{i=1}^n\frac{1}{\sqrt i}$

I'm trying to prove $$2(\sqrt{n} - 1) < \sum_{i=1}^n\frac{1}{\sqrt i}$$ (Which is the opposite pretty much of Prove by induction that $\sum_{i = 1}^{n} \frac{1}{\sqrt{i}} \leq 2\sqrt{n} - 1$) And ...
1
vote
0answers
29 views

Generalized Bernoulli's inequality of the form $\frac{1}{1-\sum_{i=1}^nx_i}\geq\prod_{i=1}^n(1+x_i)$

We got to prove the generalized Bernoulli's inequality given below for $x_1,...,x_n\geq0$ using induction. $$ \frac{1}{1-\sum_{i=1}^nx_i}\geq\prod_{i=1}^n(1+x_i)\geq 1+\sum_{i=1}^nx_i$$ The right ...
0
votes
1answer
44 views

Prove by induction that $3n^2 + 3n + 1 \leq 2(3^n)$

This is a proof within another proof but I am stuck on the last few steps of: Prove by induction that $3n^2 + 3n + 1 \leq 2(3^n)$. Any help with good explanation would be wonderful!!! Here's what ...
0
votes
1answer
20 views

Show that $\forall n \in \mathbb{N}: n$ can be written as $F_{n+1}$ different sums of ones and twos

Show that $\forall n \in \mathbb{N}: n$ can be written as $F_{n+1}$ different sums of ones and twos where the order matter. Presumably, mathematical induction can be leveraged here. Step 1: Show ...
0
votes
1answer
33 views

Prove by mathematical induction that $\forall n \geq 4 \in \mathbb{N}: 3n^2 + 3n +1 < 2(3^n)$ [duplicate]

Prove by mathematical induction that $$\forall n \geq 4 \in \mathbb{N}: 3n^2 + 3n +1 < 2(3^n)$$ Step 1: Show that the statement is true for n = 4: $$3(4)^2 + 3(4) +1 < 2(3^4)$$ Which ...
0
votes
0answers
30 views

Strong induction proof problem with $x$-cent postage stamps

I have the following example problem that has to be proven using strong induction: "Prove that every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps." ...
0
votes
1answer
22 views

Proof by induction of recurrence relation

I've been shown the following proof by induction of $P(n)$ where $n$ is a positive integer presumably. This is in the context of algorithmic analysis. $ P(n):T(n) = \begin{cases} ...
0
votes
1answer
51 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
3
votes
2answers
147 views

Proving Rational Numbers are Countable in a Different Way

Prove that positive rational numbers are countable using the partitions: $P_i= \lbrace x \in \mathbb{Q}^+ | x= {p \over{q}}, p+q=i, \gcd(p,q)=1 \rbrace$ where $\gcd(p, q)$ is the greatest common ...
4
votes
3answers
84 views

Prove even integer sum using induction

This is a homework problem, so please do not give the answer away. I must prove the following using mathematical induction: $\forall n\in\mathbb{Z^+},\;2+4+6+\cdots+2n=n^2+n.$ This is what I ...
0
votes
2answers
39 views

Proving $\sum_{i=0}^n 5^i=(5^{n+1}-1)/4$ by induction [closed]

Prove that $$ \sum_{i=0}^n 5^i = \frac{5^{n+1}-1}{4} $$ for all integers $n\geq 0$. Recall that $$ \sum_{i=0}^n a_i = a_0+a_1+\cdots+a_n. $$ This a problem from my discrete mathematics class. The ...
4
votes
2answers
72 views

Understanding this proof

I don't know how they come from the step prior to the last to the last. If somebody could explain what happens there, that would be appreciated. Thanks in advance!
1
vote
1answer
25 views

Upper Bounds Proof

The sequence $\left(s_n\right)_{n=1}^{\infty}$ is defined recursively as follows: let $s_1 = 1$, and then $s_{n+1} = \sqrt{1+2s_n}$ for $n \geq 1$. (So $s_1 = 1, s_2 = \sqrt{3}, s_3 = ...
0
votes
1answer
36 views

problem understanding induction proof for following recurrence sequence $\frac{a_{n-1}+a_{n-2}}{2}$

I've got this recurrence sequence and it's proof, but I'm stuck with the 2nd/3rd step in the induction step. $$a_0:=0, a_1:=1\\ a_n:= \frac{a_{n-1}+a_{n-2}}{2}$$ Show that for all $n\in N$: ...
0
votes
0answers
17 views

Prove simple induction [duplicate]

Suppose we we have n straight lines on the plane such that no two of them are parallel and no three of them go through the same point. Prove that the number of different regions that are created by ...
1
vote
1answer
45 views

How does $H_{k}=\displaystyle\left[H_{k+1}-\frac{1}{k+1}\right]$?

I'm confused about one of the algebraic steps, In showing the $k+1$'th term, we have: \begin{align}\displaystyle\sum\limits_{j=1}^{k+1}H_{j} &= \displaystyle\sum\limits_{j=1}^{k}H_{j} + H_{k+1} ...
0
votes
1answer
39 views

Proof by induction: form of a polynomial

Problem: Any polynomial $P_n(x)$ can be written as $P_n(x)$=$\sum_{i=0}^n c_i \alpha_i(x) $ where $\alpha_i(x)$ is a polynomial of degree exactly $i$. Attempt: Base case ($n=1$): $P_1(x)=c_0+c_1(x)$ ...
2
votes
3answers
54 views

Proof using strong induction [duplicate]

I need to prove/show that $n^3 \leq 3^n$ for all natural numbers $n$ by strong induction. I have no clue where to begin!!!! :( I know how to do the beginning steps of showing that it's true for $k = ...
3
votes
3answers
83 views

Prove $(1 +\frac{ 1}{n}) ^ {n} \ge 2$

Using induction, I proved the base case and then proceeded to prove: $$(1 + \frac{1}{n+1}) ^ {n+1} \ge 2$$ given $$(1 + \frac{1}{n}) ^ n \ge 2$$ However, I'm stuck at this point and have no clue how ...
2
votes
2answers
31 views

Prove by Induction Summation

Prove by induction: Given that $f(x) = x^{-1}$, then the $k$-th derivative of $f$ is given by $f^{\langle k\rangle}(x) = (−1)^k \cdot k!\;x^{−(k+1)}$ for all $k ≥ 1$. How do I go about proving this? ...
5
votes
2answers
169 views

What exactly is the difference between weak and strong induction?

I am having trouble seeing the difference between weak and strong induction. There are a few examples in which we can see the difference, such as reaching the $k^{th}$ rung of a ladder and ...