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

0
votes
0answers
73 views

Prove the number comparisons it takes to find the min and max of a list by the split and conquer method

Prove that the number of comparisons it takes to find the min AND max of a list by the split and conquer method (split a list in half until there are multiple subsets of just 2 elements and compare ...
5
votes
2answers
73 views

Prove: $1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+…+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$

Prove: $\displaystyle 1+{n\choose 1}\cos\phi+{n\choose 2}\cos2\phi+...+{n\choose n}\cos n\phi=2^n\cos^n\frac{\phi}{2}\cos\frac{n\phi}{2}$ I used induction: For $n=1$ equality holds. For $n=k\colon$...
-1
votes
5answers
95 views

Proof: $\sqrt[n]{n} > \sqrt[n+1]{n+1}$ [duplicate]

How can I prove that $\sqrt[n]{n} > \sqrt[n+1]{n+1}$ for $n \in \mathbb{N} \setminus \{ 1,2 \}$ ? My approach: Step 1: $n_0 := 3 \qquad \sqrt[3]{3} > \sqrt[4]{4}$ which is true. Step 2: $\...
-1
votes
2answers
41 views

Prove by induction that $\sqrt[n+1]{n+1}<\sqrt[n]{n}$ for $n\ge 3$ [duplicate]

I've been dealing with this problem for almost 2 hours now, with hardly any progress. I'm to prove the following inequality using induction $$\sqrt[n+1]{n+1}<\sqrt[n]{n}$$ where $n≥3$, $n∈\mathbb{...
0
votes
2answers
54 views

Finding a closed form for the recursively defined function using the substitution method.

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & ...
2
votes
2answers
39 views

Show that $n^{n-3} \ge n!$ for n=9, 10,…

Show that $n^{n-3} \ge n!$ for n=9, 10,... I have tried to n=9 $9^{9-3} = 9^6 = 531411$ $9! = 362880$ So $9^6 \ge 9!$ is true My question is how do I prove it by every for n=9, 10,... by ...
2
votes
1answer
179 views

Two very difficult induction proofs; having trouble with the inductive step

$$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+1}\frac{n-2k-1}{k+1} = n-2 + \frac{1}{n+1}\binom{2n}{n}$$ $$\sum_{k=0}^{n-2} \binom{n}{k}\binom{n}{k+2}\frac{n-2k-1}{k+1} = -n + \frac{n}{(n+2)(n+1)}\binom{...
3
votes
3answers
1k views

Prove by induction $\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$ for $n\ge1$ [duplicate]

Prove the following statement $S(n)$ for $n\ge1$: $$\sum_{i=1}^ni^3=\frac{n^2(n+1)^2}{4}$$ To prove the basis, I substitute $1$ for $n$ in $S(n)$: $$\sum_{i=1}^11^3=1=\frac{1^2(2)^2}{4}$$ Great. ...
0
votes
4answers
83 views

Mathematical Induction for $4 + 10 + 16 +…+ (6n−2) = n(3n +1)$

Use mathematical induction to prove: $$4 + 10 + 16 +…+ (6n−2) = n(3n +1)$$ I'm having a hard time understanding the induction process. Can someone please explain this to me?
1
vote
2answers
27 views

Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having distinct eigenvalues $a \neq b$. Show that, for all $n > 0$, $A^n = {a^n\over a − b} (A − bI) + {b^n\over b − a} (A − aI)$. I'm trying to prove ...
1
vote
1answer
50 views

Multiplying products of $p_1,p_2,\ldots,p_n$ gives a square.

Given $n+1$ ($n\ge 4$) arbitrary products of primes $p_1,p_2,\ldots, p_n$, prove multiplying some of the products gives a square. E.g., for $n=4$: $\{p_1,p_2,p_3,p_4,p_1p_3\}$ satisfies the ...
2
votes
1answer
46 views

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$.

Let $A ∈ M_{2×2}(\mathbb{C})$ be a matrix having a unique eigenvalue $c$. Show that $A^n = c^{n−1}[nA − (n − 1)cI ]$ for all $n > 0$. I'm doing induction for this, the base step when $n=1$ gives ...
3
votes
2answers
24 views

Show that the sequence $(x_n)=c^{\frac{1}{n}}$ is increasing for $0 < c < 1$.

Show that the sequence $(x_n)=c^{\frac{1}{n}}$ is increasing for $0 < c < 1$. I am trying to do this using induction. We see for the base case that $x_1 = c$ and $x_2 = c^{0.5}$, so clearly $...
4
votes
1answer
100 views

Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
0
votes
1answer
36 views

Prove recurrence relation using mathematical induction

solve recurrence relation $a_n = a_{n–1} + 12 a_{n–2}$, where $a_0 = 1$ and $a_1 = 11$ and Verify, using Principle of Mathematical Induction, that $a_n = (-1)(-3)^n + (2)(4^n)$. ans: i have done so ...
1
vote
1answer
50 views

Expand the summation (university) [closed]

Expand the summation $$\sum^{n}_{i=0}i\times i! = $$ I am studying for an exam, I have no idea what this question means.
0
votes
2answers
61 views

Induction proof fibonacci numbers

I need to prove the following with induction: n∑i=1 F(2i-1) = F(2n) for all n >= 1 I am stuck in my inductive step: n∑i=1 F(2i-1) = n∑i=1 F(2i-1) + F(2(n + 1) -1) = F(2n) + F(2(n + 1)-1) =...
1
vote
2answers
74 views

Proof by induction $\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 2$

Proof by induction $\frac{1}{1^2} + \frac{1}{2^2} + \cdots + \frac{1}{n^2} < 2 \ \ \ n \in \mathbb{N}$ So for $n=1$ $$ 1 < 2$$ For $n > 1$ Assumption: $$\frac{1}{1^2} + \frac{1}{2^2} + \...
-1
votes
3answers
68 views

Upper estimate for partial sums of the series $\sum 1/n^3$

I'm looking for a proof of: $$1 + {1\over 8} + {1 \over 27} + \dots + {1 \over n^3} < 1.5 − {1 \over n}$$ for all integers $n>2$. I have been working on proof by mathematical induction for a ...
2
votes
1answer
48 views

Proving some identities in the set of natural numbers without using induction…

I'm not sure how to prove some of the identities without using induction, for example: $$1+2+3+...+n=\frac{n(n+1)}{2}$$ $$1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$$ $$1^3+2^3+...+n^3=(\frac{n(n-1)}{2})^...
7
votes
1answer
2k views

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point. I know we start with the base case, where, ...
2
votes
1answer
35 views

Proof by induction: $ 2^n \ge n^2$ for $n\ge4$ [duplicate]

The first part is clear but in the second I did this: $2^{n+1}=2^n\cdot 2 \ge n^2\cdot 2=n^2+n^2=n^2+n\cdot n\ge n^2+n\left(2+\frac{1}{n}\right)=(n+1)^2$ I'm not sure if I the assumption: $n\ge 2+(...
0
votes
1answer
39 views

Recursive/Strong Induction

Suppose that $a_0, a_1, a_2, \dots$ is a sequence defined as follows. $$a_0 = 2, a_1 = 4, a_2 = 6 \text{, and } a_k = 7 a_{k-3} \text{ for all integers $k \ge 3$.}$$ Prove that $a_n$ is even for all ...
0
votes
3answers
124 views

Proving a closed-form recurrence by induction

Find the closed form for the following, then prove by strong induction: $$T(n) = \begin{cases} 1\quad &\text{ if } n = 0 \\ 11\quad &\text{ if } n = 1 \\ T(n-1) + 12T(n-2) & \text{ ...
1
vote
1answer
54 views

Prove if $f$ is class $C^r$, then $f^{-1}$ is of class $C^r$

Suppose that $f:(a,b)\rightarrow$ is differentiable and that $f'$ is never zero. By the inverse-function theorrem, $f$ is a bijection from $(a,b)$ onto an interval $(c,d)$, the function $f^{-1}:(c,d)\...
0
votes
6answers
1k views

Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.

Induction: Prove that $4^{n+1}+5^{2 n - 1}$ is divisible by 21 for all $n \geq 1$.
0
votes
2answers
103 views

Trees with no vertex of degree 2 have more leaves than internal nodes

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes so we want to prove this claim by induction and an answer from Micheal Biro suggested ...
0
votes
1answer
29 views

Proof by induction for inequality

Suppose $L:(0,\infty)\rightarrow \mathbb{R}$ is differentiable, that $L(1)=0$, and that $L'(x)=1/x$ for all $x>0$. Show that $L(2^n)>n/2$ for all $n\in N$. Based off of a hint I am to use the ...
1
vote
2answers
81 views

Question regarding proof by Induction

A vending machine cannot return coins as change, but only five-cent and eight-cent stamps. For a particular k, though, we can prove by induction that the machine can make every number of cents that ...
0
votes
2answers
128 views

Proving a mangled graph to be connected.

In MIT's 6.042J course, there is a question in assignment 5 problem 3 c. An n-node graph is said to be mangled if there is an edge leaving every >set of n/2 or fewer vertices. Again, as a special ...
9
votes
4answers
252 views

$n! \leq \left( \frac{n+1}{2} \right)^n$ via induction

I have to show $n! \leq \left( \frac{n+1}{2} \right)^n$ via induction. This is where I am stuck: $$\left( \frac{n+2}{2} \right)^{n+1} \geq \dots \geq =2 \left( \frac{n+1}{2} \right)^{n+1} = \...
4
votes
4answers
93 views

How to prove $n!\leq(\frac{n+1}{2})^n$ [duplicate]

Prove that for $n\in\mathbb{N}$ $$n!\leq(\frac{n+1}{2})^n.$$ I've solved base case for $n=1$ $$1\leq(\frac{1+1}{2})^1=1$$ The second step I've made was that I assumed that $n!\leq(\frac{n+1}{2})^n$ ...
4
votes
4answers
103 views

How can I show that $n! \leqslant (\frac{n+1}{2})^n$?

Show that $$n! \leqslant (\frac{n+1}{2})^n \quad \hbox{for all } n \in \mathbb{N}$$ I know that it can be done by induction but I always find line where I do not know what to do next.
3
votes
3answers
368 views

Proving that $n!≤((n+1)/2)^n$ by induction [duplicate]

I'm new to inequalities in mathematical induction and don't know how to proceed further. So far I was able to do this: $V(1): 1≤1 \text{ true}$ $V(n): n!≤((n+1)/2)^n$ $V(n+1): (n+1)!≤((n+2)/2)^{(n+...
1
vote
1answer
218 views

Flipping bits and crossing strings induction problem.

Consider a binary string consisting of n bits, where n ≥ 1. We are allowed to perform the following operation: we can replace a 1 by a x, and when we do that we must flip the two bits immediately ...
4
votes
2answers
73 views

Recurrence relationship

How do you solve the following recurrence relationship? $$x_{n} = \frac{x_{n-1}}{1 + x_{n-1}}$$ where $$ x(0) = 1 $$ I know the answer is $$ x_n = \frac{1}{n+1}$$ I solved it by induction. But I ...
4
votes
3answers
794 views

Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} > \frac{13}{24}$ for $n>1,n\in\Bbb N$ by Induction

Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} > \frac{13}{24}$ for $n>1,n\in\Bbb N$ To solve it I used induction but it is leading me nowhere my attempt was as follows: Lets ...
4
votes
4answers
147 views

How to prove this $(n+1)^n < n^{n+1}$ for $\space n \ge 3$

I'm having some more trouble with induction I know how to prove this using $\ln$, but I need to use induction only. prove that: $(n+1)^n < n^{n+1}$ for any $ n\ge 3$
3
votes
5answers
259 views

Induction: $n^{n+1} > (n+1)^n$ and $(n!)^2 \leq \left(\frac{(n + 1)(2n + 1)}{6}\right)^n$

How do I prove this by induction: $$\displaystyle n^{n+1} > (n+1)^n,\; \mbox{ for } n\geq 3$$ Thanks. What I'm doing is bunch of these induction problems for my first year math studies. I tried ...
0
votes
0answers
30 views

proof that $n! \leq (\frac{n+1}{2})^n$ [duplicate]

How do I prove the following statement using induction? $(n \in \mathbb{N})$ $$n! \leq (\frac{n+1}{2})^n$$ So for $n = 1$ it is true, since $1 \leq (\frac{2}{2})^1$. So now: Assumption: $n! \leq (\...
0
votes
3answers
55 views

proof that $n^2 + 2n \leq 5^n $

How do I prove the following statement using induction? $(n \in \mathbb{N})$ $$n^2 + 2n \leq 5^n $$ So for $n = 1$ it is true, since $1 + 2 \leq 5$. So now: Assumption: $ n^2 + 2n \leq 5^n $ ...
0
votes
1answer
158 views

2^m marbles in multiple boxes.

Let m be a non-negative integer. Suppose $2^m$ marbles are separated into several boxes. At each step we are allowed to do the following operation: Pick two boxes, say box A with p marbles and box B ...
0
votes
2answers
68 views

Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$

Prove: $\frac{(2n)!}{n!(n+1)!}\in \mathbb{N}, \forall n\in\mathbb{N}$ I used induction, for $n=k$ assume that $\frac{(2k)!}{k!(k+1)!}\in \mathbb{N}$ For $n=k+1$ $\frac{(2k+2)!}{(k+1)!(k+2)!}\in \...
0
votes
2answers
111 views

Induction proof of exponential and factorial inequality

I'm trying to find a proof for the following statement, using mathematical induction: $$ (\forall n\in \mathbb N-\{0\}) n^n \ge n! $$ But I always get to a dead-end. I've done the basis step, for $...
0
votes
1answer
48 views

how to solve this induction problem?

An m × n array A of real numbers is a Monge array if for all i, j , k and l such that 1 ≤ i < k ≤ m and 1 ≤ j < l ≤ n, we have A[i,j] + A[k,l] ≤ A[i,l] + A[k,j] In other words, whenever we pick ...
-1
votes
2answers
52 views

Summation proof- struggling to see a way to prove

I have found that the summation attached gives a general value of 1/(n+1) for the first few values of n=0,1,2,3.... I would like to prove that this is true for all n and I assumed that the best way ...
1
vote
2answers
52 views

Prove by induction: $\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$

$\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}$ For $n=1$ equality is true. For $n=m$ $m-{m\choose 2}\frac{1}{2}+...+(-1)^{m+1}\frac{1}{m}=1+\frac{...
0
votes
1answer
28 views

Is this proof of the worst-case performance of linear search correct?

I am sorry for the triviality of this question, but is this proof of the worst-case complexity of linear search correct? Claim. Let $L$ be a list of length $n$ and $k$ a target value in $L$. Then in ...
1
vote
4answers
100 views

Prove by induction: $\sum\limits_{k=1}^{n}sin(kx)=\frac{sin(\frac{n+1}{2}x)sin\frac{nx}{2}}{sin\frac{x}{2}}$

$\sum\limits_{k=1}^{n}sin(kx)=\frac{sin(\frac{n+1}{2}x)sin\frac{nx}{2}}{sin\frac{x}{2}}$ Base case: For $n=1$ $sinx=\frac{sinx\cdot sin\frac{x}{2}}{sin\frac{x}{2}}=sinx$ Induction hypothesis: For $...
1
vote
1answer
46 views

Prove by induction: $\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$

$\sum\limits_{k=1}^{n}\frac{1}{2^k}\tan\frac{x}{2^k}=\frac{1}{2^n}\cot\frac{x}{2^n}-\cot x,x\neq k\pi,k\in \mathbb{Z}$ Base Case: For $n=1$, $\frac{1}{2}\tan\frac{x}{2}=\frac{1}{2}\cot\frac{x}{2}-\...