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
1answer
32 views

Use Complete Induction of set theory to prove .

Proove by the Complete Induction for every $n\in \mathbb{N}, n \geq 1$ $$\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + ... + \frac{1}{\sqrt{n}} > \sqrt{n}$$. I know only the basis ...
0
votes
1answer
33 views

Use strong induction to prove that $f_n = g_n$ for all $n \in \mathbb{N}$.

I would like to use strong induction to prove that $f_n = g_n \; \forall n \in \mathbb{N}$, where $f_n$ is defined as: $f_0 = 1 \\ f_1 = 5 \\ f_2 = 10 \\ f_n = 2f_{n-1} - 4f_{n-2} \; \text{for $n \...
1
vote
1answer
58 views

Showing $\frac{d^2}{dr^2}\left(\frac{1}{r}\frac{d}{dr}\right)^{k-1}(r^{2k-1}\phi(r))=\left(\frac{1}{r}\frac{d}{dr}\right)^{k}(r^{2k}\phi'(r))$

How to show that $\frac{d^2}{dr^2}\left(\frac{1}{r}\frac{d}{dr}\right)^{k-1}(r^{2k-1}\phi(r))=\left(\frac{1}{r}\frac{d}{dr}\right)^{k}(r^{2k}\phi'(r))$ for $k\ge 1, r>0$ and $\phi$ sufficiently ...
0
votes
0answers
10 views

bound $\delta_{s+1}$ from $\delta_s - \frac{1}{2\beta \| x_1 - x^\star \|^2} \delta_{s+1}^2$

The origin of the problem is on page 271, Convex optimization: Algorithm and complexity Given a function $f$ convex and $\beta$-smooth. Define $\delta_s = f(x_s) - f(x^\star)$, where $x_s$ is the ...
1
vote
5answers
89 views

Showing that $n! > n^2$ for $n\geq4$ by induction

My attempt: Prove $ n! > n^2 $ for $ n \geq 4 $ Base Case: $P(4) = 24 > 16$ Inductive Hypothesis $P(k) : k! > k^2 $ $P(k+1) : (k+1)! > (k+1)^2 $ $ (k + 1)! - (k+1)^2 > 0 $ $ (k+...
3
votes
1answer
57 views

Is this proof valid? The claim is $2^{k} < (k+1)!$ for $k \geq 2$

Hey guys so I think I have completed this proof but I'm not sure if its valid. Here it is: Prove that $ 2^n < (n+1)! \quad\text{for}\quad n >= 2 $ Here is my proof: Base Case P(2) = $ 4 < ...
0
votes
1answer
55 views

How can I prove this by mathematical induction [closed]

$n!>n^{n/2}$. For every positive integer greater than $2$
-1
votes
1answer
28 views

Proof binomial coefficient [closed]

I'm trying to prove the following: $$\binom{n + p}{k} = \sum_{j=0}^n \binom{n}{j} \cdot \binom{p}{k - j}$$ How do I do it? Induction? And can someone hint me at how to start?
1
vote
1answer
64 views

Mathematical induction proof problem: $\sum_{i=1}^{n-1} i(i+1) = \frac{n(n+1)(n-1)}3$

I am having difficulty proving the inductive hypothesis $(k+1)$ for the following statement: $$\sum_{i=1}^{n-1} (i(i+1)) = \frac{(n)(n+1)(n-1)}{3}$$ This is what I have so far: $$(Step \ 1) \sum_{i=...
0
votes
1answer
41 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = k+1$$$T_{...
1
vote
1answer
56 views

Induction Proof $2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{ 2}$

I am looking for an induction proof... $$2 + 5 + 8 + 11 + \cdots + (9n - 1) = \frac{3n(9n + 1)}{2}$$ when $n \geq 1$. I know there are $3$ steps to this. 1) Check 2) Do $n = k$ 3) Do $n = k + 1$ ...
4
votes
1answer
44 views

An inequality $\frac1{(n+1)^{1/(n+1)}}-\frac1{n^{1/n}}\le \frac1{n+1}$

I have graphed the functions $f,g:\mathbb{R^+}\to\mathbb{R}$ defined by $$f(x)=\frac1{(x+1)^{1/(x+1)}}-\frac1{x^{1/x}}\mbox{ and } g(x)=\frac1{x+1}$$ and it seems like $f(x)\le g(x)$ for all $x>0$. ...
2
votes
2answers
56 views

Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) ...
0
votes
1answer
33 views

Prove inequality $\frac{a_1a_2…a_n}{(a_1+a_2+…+a_n)^n}\le \frac{(1-a_1)(1-a_2)…(1-a_n)}{(n-a_1-a_2-…-a_n)^n}$

Let $n\in \mathbb N, a_1,a_2, ...,a_n\in \left(0,\frac 12 \right]$. Prove inequality: $$\frac{a_1a_2...a_n}{(a_1+a_2+...+a_n)^n}\le \frac{(1-a_1)(1-a_2)...(1-a_n)}{(n-a_1-a_2-...-a_n)^n}$$ My work ...
2
votes
2answers
33 views

Prove that if $n \in \mathbb{N}$ and $n \ge 2$, then $2^{n + 1} \le 3^n$.

Prove that if $n \in \mathbb{N}$ and $n \ge 2$, then $2^{n + 1} \le 3^n$. My method: If $n = 2$, $2^{n + 1} \le 3^n$ then $2^3 \le 3^2$ is $8 \le 9$, which holds for $n = 2$. $2^{k + 1} \le 3^k$ ...
1
vote
2answers
29 views

Use induction to prove that $2^n \gt n^3$ for every integer $n \ge 10$.

Use induction to prove that $2^n \gt n^3$ for every integer $n \ge 10$. My method: If $n = 10$, $2^n \gt n^3$ where $2^{10} \gt 10^3$ which is equivalent to $1024 \gt 1000$, which holds for $n = 10$....
0
votes
2answers
36 views

Use the rule for differentiating a product to prove that the derivative of $x^n$ is $nx^{n-1}$ for all $n∈N$.

I know the rule of differentiation, but to proving why the derivative is that is my problem. Should I be proving this question by induction because that's what I've been learning.
2
votes
3answers
46 views

Prove that $\sum_{k=1}^n \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k}(-1)^{k-1}$ using induction [duplicate]

I'm trying to prove (using induction) that: $$\sum_{k=1}^n \frac{1}{n+k} = \sum_{k=1}^{2n} \frac{1}{k}(-1)^{k-1}.$$ I have found problems when I tried to establish an induction hypothesis and ...
2
votes
3answers
30 views

Induction to prove that for any $r \in \mathbb{R}$ such tht $r \notin (0,1)$ $\sum_{i=1}^n r^i-1 = \frac{(1-r^n)}{1-r}$ for all $n \in \mathbb{N}$.

Use induction to prove that for any $r \in \mathbb{R}$ such that $r \notin (0,1)$ $$\sum_{i=1}^n r^{i-1} = \frac{1-r^n}{1-r}$$ for all $n \in \mathbb{N}$. My method: Assume $$\sum_{i=1}^k r^{i-1} = \...
2
votes
2answers
39 views

Prove by induction that $\sum_{k=1}^nk^p < (n+1)^{p+1}/(p+1), \quad n,p \in \mathbb{N}$

For $n=1$, we have at the left side $1^p$, and at the right side: $$ \frac{2^{p+1}}{p+1}\mathrm{~which~is } >1$$ so it holds for $n=1$, but how can we prove that $$ \sum_{k=1}^{n+1}k^p<\frac{(n+...
3
votes
3answers
55 views

An induction problem that I can't think of an approach.

Prove that if $n$ people are standing on line at a ticket counter, and the first person on line is a woman and the last is a man, then somewhere on the line there is a man standing directly behind a ...
0
votes
0answers
19 views

Symmetric Positive Matrix Diagonal Value relationships after Gaussian Elimination

Let $A\in\mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Let Gaussian elimination be carried out on $A$ without pivoting. After $k$ steps, $A$ will be reduced to the form $$A^{(k)}=\...
0
votes
2answers
44 views

Proving a $\cos(2nx)$ identity using induction

Prove that $\cos(2nx)=∑_{k=0}^n (-1)^k \dbinom{2n}{2k} \cos^{2(n-k)}(x)\cdot \sin^{2k}(x):=p(n)$ I'd start using induction, with $n=1$ we have: $$cos(2x)=\cos^2(x)-\sin^2(x)$$ True. Now assume $p(n)...
-2
votes
2answers
29 views

proove that any postage greater than 17 can be made using 4 and 7 cent stamps

Please use strong induction for the problem. I know that regular induction doesn't work. I assume there is a proof by logic by simply saying that 18, 19 and 20 cents can be made using these stamps and ...
2
votes
3answers
59 views

Establish by mathematical induction that a set having $n$ elements has $2^n$ subsets.

I know the steps to an induction proof. The first step is to establish that $n=1$ is true. Then the second step is to assume that if we replaced $n$ by $k$, $2^k$ is true. For the third step, assuming ...
0
votes
5answers
70 views

Prove by induction: A tree on n≥2 vertices has ≥2 leaves

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction? Base Case: $P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the ...
0
votes
0answers
25 views

Proving running time with induction

I need to use induction to prove the run time of the given recurrences: $T(1) = c_1$ $T(n) = T(n-1) + c_2$ Well this is the first time Im doing induction on this kind of exercise - I would like ...
1
vote
1answer
30 views

Proof by strong induction combinatorics problem

$1(1!) + 2(2!) + 3(3!) + \dots + n(n!) = (n+1)! - 1$ How do we prove this by strong induction? I know how to do it with weak induction, but how would strong induction work with this problem?
3
votes
1answer
38 views

Prove that in every WFF, there is a logical connective between every two atoms.

First, I have defined a well-formed formula as such: 1) Each atom is a WFF. 2) If φ is a WFF, so is ¬φ 3) If φ and ψ are WFFs, if ∗ is a binary connected (i.e., ∨,∧,→), then (φ∗ψ) is a WFF. What ...
0
votes
1answer
20 views

Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
0
votes
2answers
57 views

$\sum_{k=1}^n 1/k - \log n$

I got this question : $$a_n = \sum_{k=1}^n \frac 1k - \log n$$ I proved that $\lim a_n $ exist. Now I have to prove: $$ 0<a_n-\lim a_n\le \frac 1n $$ for every $n \in \mathbb N$. I tried ...
3
votes
0answers
35 views

Delete some numbers in $x_1+x_2+…+x_n=y_1+y_2+…+y_m<mn$

Let $$x_1+x_2+...+x_n=y_1+y_2+...+y_m<mn,$$ where $x_i,y_i -$ positive integers. Prove that you can delete some terms (but not all) in the equation and equality remains true. My work so ...
2
votes
2answers
64 views

Why can we assume a statement is true for $n = k$, when using induction? [duplicate]

I know the principle of mathematical induction. The only thing that causes my confusion is that we suppose a statement is true for $n=k$ then we prove the statement is also true for $n=k+1$ but how ...
1
vote
0answers
31 views

Help understanding one of Euler's theorem in Number Theory [duplicate]

I am looking at two Euler's theorems in my textbook which are the following: If $p$ is prime and $a$ is any whole number, then $(a+1)^p - (a^p + 1) $ is evenly divisible by $p$. If $p$ is prime and $...
1
vote
2answers
52 views

Hint for prove $\forall n \in \Bbb N \sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$?

I'm trying to prove the following inequality $\forall n \in \Bbb N$: $$\sum _{i=1}^{n} \frac {1}{i!} \le 2 - \frac{1}{2^{n-1}}$$ I'm doing it by induction. It's true for $P(1)$. So now I want to ...
-7
votes
0answers
43 views

Mathematical proof by induction. [duplicate]

How to prove the following using mathematical proof by induction? $\phi^n = \phi\times F_n + F_{n-1}$ $\phi = 1 + \sqrt 5 /2$ Fn is the Fibonacci number. I tried solving this using induction but ...
2
votes
0answers
31 views

Suppose that $a, b ∈ N$ are relatively prime. Prove that, for any $k ∈ N$, $a^k$ and $b$ are relatively prime.

Note: I've asked this question before, but this one offers a proposed solution and I'm checking for verification. $a$ and $b$ are relatively prime if the greatest common divisor of them is $1$. I am ...
0
votes
3answers
97 views

Prove $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ using mathematical induction.

I need to prove the following equation using mathematical induction and using the phi values if necessary. $\phi^n = \phi F_n + \text{(another Fibonacci number)}$ In this proof, it is kind of hard ...
-1
votes
2answers
30 views

By induction prove $\prod _{i=1}^{n} \frac{n+i}{2i-3} = 2^n (1 - 2n)$

I need to prove the following by induction. $\forall n \in \Bbb N$ $\prod _{i=1}^{n} \frac{n+i}{2i-3} = 2^n (1 - 2n)$ I know the steps to take but I'm failing to come to the right side of the ...
0
votes
1answer
40 views

proving the inequality $ (\frac{n}{e})^n \leq n! \leq en ( \frac{n}{e})^n$ by induction

I want to prove $ (\frac{n}{e})^n \leq n! \leq en ( \frac{n}{e})^n$ by induction. For this prove I want to use the inequality $(\frac{n+1}{n})^n < e <(\frac{n+1}{n})^{n+1}$. for $n=1$ the ...
1
vote
1answer
15 views

Solution check: summation inequality proof by induction

I'm not sure if what I've done works or if it's proof enough. (I need to prove that the inequality is true $\forall n \in \mathbb{N}$). $\sum_{i=n}^{2n} \frac{i}{2^i} \leq n$ $P(1)$ works. I assume ...
0
votes
0answers
17 views

Solve using math induction with steps. [duplicate]

$$\sum_{i=1}^{n+1} i2^i = n2^{n+2} + 2, \forall n \geq 0$$ Getting stuck.
2
votes
1answer
33 views

How to prove by induction that $\frac{a^n+b^n}{2}\geq\left(\frac{a+b}{2}\right)^n$?

I'm about to prove that for any $a,b>0$ and $n\in\mathbb{N},$ the inequality: $\frac{a^n+b^n}{2}\geq\left(\frac{a+b}{2}\right)^n$ holds. By induction I get: $$\left(\frac{a+b}{2}\right)\cdot\frac{...
0
votes
1answer
50 views

Strong Induction Proof of amounts of money

I am so confused about this kind of question which is referring to amounts of money. I know we should use strong induction to prove if we meet some questions asking you which amounts of money can be ...
1
vote
2answers
52 views

How can you prove this by strong induction?

The sequence $b_1,b_2,...$ is defined recursively as:\begin{align} b_1&=0;\\ b_2&=1;\\ b_n&=2b_{n-1}-2b_{n-2}-1 \ \text{for} \ n\geq3. \end{align} Prove that this means: $$\forall n\geq1: ...
1
vote
1answer
22 views

induction with 2 recursive sequnces

I'm having trouble solving this problem. I have relation for two sequences of natural numbers. $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$ and I have to prove that recursions: $$\begin{align*...
1
vote
2answers
41 views

Prove by induction that $I_n = \frac{4^{n+1}n!(n+1)!}{(2n+3)!}$

$I_n$ is defined as: $$I_n = \int_{0}^{1} \big[x^n \sqrt{1-x}\big] dx$$ Let $p(n)$ be the statement: $$I_n = \frac{4^{n+1}n!(n+1)!}{(2n+3)!}$$ Prove by mathematical induction $p(n)$ is true for n =...
2
votes
2answers
40 views

Induction proof of the identity $\cos x+\cos(2x)+\cdots+\cos (nx) = \frac{\sin(\frac{nx}{2})\cos\frac{(n+1)x}{2}}{\sin(\frac{x}{2})}$ [duplicate]

Prove that:$$\cos x+\cos(2x)+\cdots+\cos (nx)=\frac{\sin(\frac{nx}{2})\cos\frac{(n+1)x}{2}}{\sin(\frac{x}{2})}.\ (1)$$ My attempt:$$\sin\left(\frac{x}{2}\right)\sum_{k=1}^{n}\cos{(kx)}$$$$=\sum_{k=1}...
1
vote
5answers
60 views

Prove $\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$ [duplicate]

Prove $$\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$$ Proof by induction: true for $n=2$. Assume true for $n$ and see if $n+1$ is true. $$\sum _{k=2}^{n} k(k-1) {n \choose k}=n(n-1)2^{n-2}$$ ...
3
votes
3answers
54 views

Prove $b-a \le \sum^n_{i=1}(b_i-a_i)$ by induction

Show that if the closed interval $[a,b]$ is covered by finitely many open intervals $(a_1,b_1), ...,(a_n,b_n)$, then $$b-a \le \sum^n_{i=1}(b_i-a_i)$$. I know that $(a_1,b_1), ...,(a_n,b_n)$ form an ...