0
votes
2answers
53 views

Using induction to prove a formula for $\sin x+\sin 3x+\dots+\sin (2n-1)x$

I'm working from the text "Intro To Real Analysis" by William Trench. Here is what I have thus far. I will prove using Mathematical Induction that $\sin x+\sin 3x+...+\sin (2n-1)x=\frac{1-\cos ...
1
vote
3answers
38 views

Prove a sum formula by induction

I am to prove through induction that $$\sum_{k=1}^n (2k-1)^2 = \frac{n(2n-1)(2n+1)}{3}$$ And well, my method seems to be working, but I get stuck when I'm nearly done. First I prove the formula work ...
0
votes
2answers
60 views

Sum of the first $n$ numbers that is neither divisible by 2 nor 3.

Show that the sum of the first $n$ positive integers that are divisible by neither 2 nor 3 is $\frac{3}{2}n^2-\frac{1}{2}$ if $n$ is odd and is $\frac{3}{2}n^2$ if $n$ is even. I have verified that ...
5
votes
5answers
212 views

Need to prove inequality $\sum\limits_{k=0}^n \frac{1}{(n+k)} \ge \frac{2}{3}$

Prove that for $n \geq 1$: $$\sum\limits_{k=0}^n \frac{1}{(n+k)} \ge \frac{2}{3}$$ I have tried math induction but that didn't work. Although I'm pretty sure that the solving can be done by induction ...
6
votes
1answer
128 views

Prove |cos(x−1)|+|cos(x)|+|cos(x+1)|≥3/2

I'm working on an induction proof, but I keep coming up against a brick wall. While working through the induction proof process I keep ending up with $$|\cos(m)|\ge\frac12$$ ,but clearly this isn't ...
1
vote
2answers
47 views

Using induction to prove that $\sum_{r=1}^n r\cdot r! =(n+1)! -1$

Use induction to prove that $\displaystyle\sum_{r=1}^n r\cdot r! =(n+1)! -1$ I first showed that the formula holds true for $n=1$. Then I put n as $k$ and got an expression for the sum in ...
1
vote
2answers
70 views

Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.
-1
votes
1answer
65 views

Proof by Induction [Number Theory by George E. Andrews 1-1 #2] [duplicate]

I am to use mathematical induction to prove that: $$1^3 + 2^3 + 3^3 + \cdots + n^3 = (1 + 2 + 3 + \cdots + n)^2 $$
2
votes
2answers
94 views

Proof of equality $\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $ by induction

I have a problem with following equality: $$\sum_{k=0}^{m}k^n = \sum_{k=0}^{n}k!{m+1\choose k+1} \left\{^n_k \right\} $$ And I would like to use induction in following way: Base: $$ m = n $$ And: $$ ...
3
votes
1answer
83 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
1
vote
1answer
40 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
3
votes
2answers
90 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
0
votes
2answers
54 views

How to derive these inequalities?

I can derive the inequalities $$ n^p < \frac{(n+1)^{p+1} - n^{p+1}}{p+1} < (n+1)^p $$ for any positive integers $p$ and $n$. These actually follow from the identity $$b^p - a^p = (b-a)(b^{p-1} + ...
1
vote
1answer
69 views

Proving Hermite's identity using induction

Can someone help me? This should be easy but I couldn't find it on any book or the internet. $$ \sum_{k=0}^{n-1}\left\lfloor x + \frac{k}{n}\right\rfloor = \lfloor nx \rfloor $$
3
votes
1answer
41 views

$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}}$

I'm supopsed to show that if $m$ and $n$ are non-negative integers then $$\sum_{k=0}^{n}(-1)^k {{m+1}\choose{k}}{{m+n-k}\choose{m}} = \left\{ \begin{array}{l l} 1 & \quad \text{if $n=0$}\\ ...
1
vote
4answers
73 views

Find a formula for $1 + 3 + 5 + … +(2n - 1)$, for $n \ge 1$, and prove that your formula is correct.

I think the formula is $n^2$. Define $p(n): 1 + 3 + 5 + \ldots +(2n − 1) = n^2$ Then $p(n + 1): 1 + 3 + 5 + \ldots +(2n − 1) + 2n = (n + 1)^2$ So $p(n + 1): n^2 + 2n = (n + 1)^2$ The equality ...
1
vote
1answer
31 views

Summation Induction when lower limit is not 1

The question is use induction to prove that $$\sum_{r=2}^n (r^2+r+1)r! = (n+1)^2n!-4$$ I don't understand how to even get the P1 statement since when I substitute r = 2 into the LHS and n = 1 into ...
2
votes
5answers
112 views

Proof via induction $1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$ This is the second part of a two part question. Part (a) was the following: ...
1
vote
2answers
118 views

Use the recursive definition of summation together with mathematical induction to prove a sequence

Use the recursive definition of summation together with mathematical induction to prove that for all positive integers $n$ if $a_1, a_2,\ldots, a_n$ are real numbers, then $$\sum_{k=1}^n(3a_k - 2k + ...
0
votes
3answers
55 views

Finding the Formula For the Sum of a Sequence

In the problem below, It is asked to find the formula for the sum of the sequence and then to prove whether it is true or false for all n values using induction. $$ 1 + 4 + 7 + ... + (3n + 1), \ n\in ...
1
vote
1answer
30 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
54 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
-1
votes
1answer
93 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...
0
votes
2answers
51 views

Inductive proof and summation

The problem asks me to prove by induction that: $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ I've worked through it at least half a dozen times, checked my math fastidiously, can't seem to figure it ...
0
votes
3answers
33 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
1
vote
1answer
88 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
3
votes
2answers
60 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
0
votes
1answer
39 views

Using induction to prove $\sum\limits^n_{k=1} 9^k = 0.5 \cdot \sum\limits^{2n}_{k=1} (-1)^k \cdot 3^{k+1}$

$$\sum^n_{k=1} 9^k = 0.5 \cdot \left[\sum^{2n}_{k=1} (-1)^k \cdot 3^{k+1}\right]$$ I have tested both with a python script and it seems to be correct. For the life of me, I am unable to unwind the ...
1
vote
2answers
68 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
1
vote
2answers
51 views

How can I come up with a formula for this summation?

I have to come up with a formula for: $$\sum_{0\le i\le n\text{, i is even}}^\ i^2$$ and then prove it by using induction. I know how to do the proof, but I am stuck on coming up with the formula. I ...
1
vote
4answers
289 views

Mathematical Induction (summation): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$

I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign. Using ...
3
votes
2answers
350 views

Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$

The question: show by using induction that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$ My attempt at a solution: The base case $n = 1$ is true. First we use the ...
1
vote
2answers
251 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
2
votes
2answers
206 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
2
votes
6answers
239 views

Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear

It's about proving the following: $$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ I understand every step in the master solution, however, I have no idea how one can know by intuition to ...
0
votes
1answer
104 views

Binomial coefficients identity (sum of the powers of the natural numbers)

I've found exercise with binomial coefficients in Kostrikin's book. Proof that $\sum_{i=1}^n{{r+1}\choose{i}}\left(1^i+2^i+\dots+n^i\right)=(n+1)^{r+1}-(n+1)$ I was trying to check that for ...
5
votes
3answers
248 views

Given n $\in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
3
votes
2answers
87 views

Prove that $\sum_{k=0}^n\frac{1}{k!}\geq \left(1+\frac{1}{n}\right)^n$ [duplicate]

It basically says it all in the title. I tried solving the inequality using the bernoulli inequality somehow $$\dfrac{\displaystyle\sum_{k=0}^n\frac{1}{k!}}{(1+\frac{1}{n})^n}\geq 1,$$ but the ...
1
vote
1answer
166 views

Prove a summation inequality by induction

I was having trouble proving by induction with this problem. $$\sum_{i=1}^n \frac{3}{4^i} < 1$$ for all $n \geq 2$ I went to see my professor and he said try proving this equality ...
4
votes
4answers
131 views

Prove that $1+a+a^2+\cdots+a^n=(1-a^{n+1})/(1-a)$.

I have problem. Prove this using Mathematical Induction. I am a newbie in Mathematics. Please help me. $$1+a+a^2+\cdots+a^n = \frac{1-a^{n+1}}{1-a}$$ This is my way for get the proof Basic ...
2
votes
3answers
95 views

How do you solve a recurrence with a summation function inside

Show that $$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$ is the same as $$t(n) = 2^n$$ Initial condition $t(0) = 1$
4
votes
2answers
81 views

Prove by mathematical induction that $\sum_{i=1}^{n}\frac{i}{2^i}\leq2$ for $n\ge 1$

I have this exercise by my professor that I have no idea how to solve. Any help would be greatly appreciated: Using the method of mathematical induction show that for all $n \geq 1$, $n ...
0
votes
2answers
56 views

Prove $\sum_{i=1}^{n}i\left(\begin{array}{c} n\\ i \end{array}\right)=n2^{n-1}$ using induction.

I have already derived the formula $\sum_{i=1}^{n}i\left(\begin{array}{c}n\\i \end{array}\right)=n2^{n-1}$ directly just by doing some algebraic manipulations to the summand, which is indeed proves ...
1
vote
2answers
85 views

How do I prove $2^{n+1} + 2n + 1 = 2^{n+2} - 1$

I am attempting to prove using induction: $\sum_0^n 2i = 2^{n + 1} - 1$ I have gotten to the point where I need to show: $2^{n+1} + 2n + 1 = 2^{n+2} - 1$ How do I prove this? Or should I be ...
0
votes
1answer
67 views

Proof by induction that $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ [duplicate]

How would I go about solving this question? Use induction to prove that for all integers $n ≥ 1$, $$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$$
0
votes
1answer
65 views

Inequality with a sum and factorial

For a homework assignment we have the following question that I'm stuck on. Let $ 0 \leq y \leq 1 $ be given. $\forall m \in \mathbb{N}$, define $ \displaystyle S_m(y)=\sum_{k=0}^m \binom{m}{k}y^k$. ...
0
votes
2answers
444 views

Induction step for $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

I want to prove by induction that, $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ OK I got the initial step, however, I have problems with the induction step: Here is what I tried: ...
3
votes
2answers
182 views

Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$

everyone. I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states: $$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$. I ...
1
vote
1answer
94 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
1
vote
1answer
48 views

Inductive demonstration

I have this: $$1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}6$$ So I was suggested of doing this: $$\begin{align} (1^2+2^2+3^2+\dots+k^2)+(k+1)^2 &= \frac{k(k+1)(2k+1)}6+(k+1)^2 \\ &= ...