Questions about evaluating summations, especially finite summations. For infinite series, please consider the (sequences-and-series) tag instead.

learn more… | top users | synonyms

64
votes
17answers
4k views

Proving the identity $\sum\limits_{k=1}^n {k^3} = {\Large(}\sum\limits_{k=1}^n k{\Large)}^2$ without induction

I recently proved that $$ \sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k \right)^2 $$ Using mathematical induction. I'm interested if there's an intuitive explanation, or even a combinatorial ...
31
votes
20answers
6k views

Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?

I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals: $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$ I really ...
21
votes
19answers
11k views

Proof for formula for sum of sequence $1+2+3+\ldots+n$?

Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$. How? What's the proof? Or maybe it is self apparent just looking at the above? Does this problem have a name and maybe a presence on the net? ...
23
votes
9answers
1k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
6
votes
1answer
1k views

Finite Sum of Power?

Sorry for the remedial math but: Can someone tell me how to get a closed form for $$\sum_{k=1}^n k^x$$ For $x = 1$, it's just the classic $n(n+1)/2$. What is it for $x > 1$?
10
votes
4answers
2k views

What is the term for a factorial type operation, but with summation instead of products?

(Pardon if this seems a bit beginner, this is my first post in math - trying to improve my knowledge while tackling Project Euler problems) I'm aware of Sigma notation, but is there a function/name ...
11
votes
4answers
1k views

Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

I'm well aware of the combinatorial variant of the proof, i.e. noting that each formula is a different representation for the number of subsets of a set of $n$ elements. I'm curious if there's a ...
10
votes
4answers
494 views

Proving $1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ using induction

How can I prove that $$1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$ for all $n \in \mathbb{N}$? I am looking for a proof using mathematical induction. Thanks
3
votes
8answers
541 views

How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?

Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$ how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2. $$ Thank you
5
votes
3answers
1k views

Proving $\sum\limits_{k=0}^{n}\cos(kx)=\frac{1}{2}+\frac{\sin(\frac{2n+1}{2}x)}{2\sin(x/2)}$

I am being asked to prove that $$\sum\limits_{k=0}^{n}\cos(kx)=\frac{1}{2}+\frac{\sin(\frac{2n+1}{2}x)}{2\sin(x/2)}$$ I have some progress made, but I am stuck and could use some help. What I did: ...
7
votes
10answers
2k views

How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

I am trying to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$ but am not able to think something except induction,which is of-course not necessary (I think) here, so I am ...
22
votes
3answers
2k views

The sum of an uncountable number of positive numbers

Claim:If $(x_\alpha)_{\alpha\in A}$ is a collection of real numbers $x_\alpha\in [0,\infty]$ such that $\sum_{\alpha\in A}x_\alpha<\infty$, then $x_\alpha=0$ for all but at most countably many ...
13
votes
8answers
1k views

How to determine equation for $\sum_{k=1}^n k^3$

How do you find an algebraic formula for $\sum_{k=1}^n k^3$? I am able to find one for $\sum_{k=1}^n k^2$, but not $k^3$. Any hints would be appreciated.
2
votes
3answers
299 views

Vandermonde's Identity : Summations with binomial coefficients

(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Pr, 8th ed by Sheldon Ross. Can someone help me solve this equation? How to prove that ...
5
votes
4answers
421 views

Proving a special case of the binomial theorem: $\sum^{k}_{m=0}\binom{k}{m} = 2^k$ [duplicate]

I want to know if I can get some help with this proof. I tried, but I just cannot seem to get $2^{k}$. It states that, For $k \in \mathbb{Z}_{\ge 0}$, $$\sum^{k}_{m=0}\binom{k}{m} = 2^k$$ Thank ...
17
votes
6answers
2k views

Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: ...
11
votes
1answer
6k views

Combinatorial proof of summation of $\sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$

Can you guys help me prove this? There is a way of proving this logically but I was hoping to find a more "mathematical" proof, if possible. $$\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n ...
5
votes
2answers
573 views

How to find the sum of this series : $1+\frac{1}{2}+ \frac{1}{3}+\frac{1}{4}+\dots+\frac{1}{n}$

Problem : How to find the sum of this series : $1+\frac{1}{2}+ \frac{1}{3}+\frac{1}{4}+\dots+\frac{1}{n}$ This is a Harmonic progression : So is this formula correct to sum the series : ...
1
vote
2answers
629 views

Induction proof concerning a sum of binomial coefficients: $\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$

I'm looking for a proof of this identity but where j=m not j=0 http://www.proofwiki.org/wiki/Sum_of_Binomial_Coefficients_over_Upper_Index $$\sum_{j=m}^n\binom{j}{m}=\binom{n+1}{m+1}$$
11
votes
0answers
556 views

Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?

Edward Waring, asks whether for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers ...
4
votes
3answers
365 views

induction proof: $\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$

I encountered the following induction proof on a practice exam for calculus: $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$ I have to prove this statement with induction. Can anyone please help me ...
2
votes
5answers
1k views

Proof via Induction for A Summation

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: $$ ...
0
votes
2answers
648 views

Proving $\sum\limits_{i=0}^n i 2^{i-1} = (n+1) 2^n - 1$ by induction

I'm trying to apply an induction proof to show that $((n+1) 2^n - 1 $ is the sum of $(i 2^{i-1})$ from $0$ to $n$. the base case: L.H.S = R.H.S we assume that $(k+1) 2^k - 1 $ is true. we need to ...
19
votes
3answers
414 views

Closed form for $\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n}$

Please help me to find a closed form for the sum $$\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n},$$ where $H_n$ are harmonic numbers: $$H_n=\sum_{k=1}^n\frac{1}{k}=\frac{\Gamma'(n+1)}{n!}+\gamma.$$
4
votes
4answers
4k views

How does the sum of the series “$1 + 2 + 3 + 4 + 5 + 6\ldots$” to infinity = “$-1/12$”? [duplicate]

(I was requested to edit the question to explain why it is different that a proposed duplicate question. This seems counterproductive to do here, inside the question it self, but that is what I have ...
11
votes
3answers
2k views

How to prove Lagrange trigonometric identity [duplicate]

I would to prove that $$1+\cos \theta+\cos 2\theta+\ldots+\cos n\theta =\displaystyle\frac{1}{2}+ \frac{\sin\left[(2n+1)\frac{\theta}{2}\right]}{2\sin\left(\frac{\theta}{2}\right)}$$ given that ...
9
votes
6answers
1k views

Proving $\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$ with induction

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum\limits_{k=1}^{n}{\frac{1}{\sqrt{k}}\ge\sqrt{n}}$$ ...
4
votes
7answers
721 views

How do I come up with a function to count a pyramid of apples?

My algebra book has a quick practical example at the beginning of the chapter on polynomials and their functions. Unfortunately it just says "this is why polynomial functions are important" and moves ...
1
vote
2answers
11k views

How to get to the formula for the sum of squares of first n numbers? [duplicate]

Possible Duplicate: How do I come up with a function to count a pyramid of apples? Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$? Finite Sum of Power? I know that the sum ...
1
vote
4answers
7k views

Is the sum of all natural numbers $-\frac{1}{12}$? [duplicate]

My friend showed me this youtube video in which the speakers present a line of reasoning as to why $$ \sum_{n=1}^\infty n = -\frac{1}{12} $$ My reasoning, however, tells me that the previous ...
0
votes
2answers
806 views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
0
votes
5answers
144 views

Prove by induction: $2^n = C(n,0) + C(n,1) + \cdots + C(n,n)$ [duplicate]

This is a question I came across in an old midterm and I'm not sure how to do it. Any help is appreciated. $$2^n = C(n,0) + C(n,1) + \cdots + C(n,n).$$ Prove this statement is true for all $n ...
19
votes
4answers
455 views

How close can $\sum_{k=1}^n \sqrt{k}$ be to an integer?

How close can $S(n) = \sum_{k=1}^n \sqrt{k}$ be to an integer? Is there some $f(n)$ such that, if $I(x)$ is the closest integer to $x$, then $|S(n)-I(S(n))|\ge f(n)$ (such as $1/n^2$, $e^{-n}$, ...). ...
5
votes
3answers
277 views

Evaluating $\sum_{n=1}^\infty\frac{x^{3n}}{(3n-1)!}$

How can we obtain following formula? $$\sum_{n=1}^\infty\frac{x^{3n}}{(3n-1)!}=\frac{1}{3}e^{\frac{-x}{2}}x\left(e^{\frac{3x}{2}}-2\sin\left(\frac{\pi+3\sqrt{3}x}{6}\right)\right).$$ I think if we ...
5
votes
2answers
2k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
5
votes
3answers
172 views

How do I evaluate this sum(involving the floor function)?

$$ \sum_{i=1}^N\left\lfloor\frac{N}{i}\right\rfloor $$ Is there a closed form expression to the above sum? (Mathematica doesn't give me anything)
20
votes
5answers
535 views

How find this sum $\sum\limits_{n=0}^{\infty}\frac{1}{(3n+1)(3n+2)(3n+3)}$

Find this sum $$I=\sum_{n=0}^{\infty}\dfrac{1}{(3n+1)(3n+2)(3n+3)}$$ My try: let $$f(x)=\sum_{n=0}^{\infty}\dfrac{x^{3n+3}}{(3n+1)(3n+2)(3n+3)},|x|\le 1$$ then we have ...
18
votes
1answer
758 views

Solving $x^k+(x+1)^k+(x+2)^k+\cdots+(x+k-1)^k=(x+k)^k$ for $k\in\mathbb N$

Letting $k$ be a natural number, can we solve the following $k$-th degree equation ? $$x^k+(x+1)^k+(x+2)^k+\cdots+(x+k-1)^k=(x+k)^k\ \ \ \ \cdots(\star).$$ The following two are famous: ...
11
votes
5answers
387 views

Combinatorial interpretation of an alternating binomial sum

Let $n$ be a fixed natural number. I have reason to believe that $$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$ for all $0\leq k \leq n.$ However I can not prove this. Any method to prove ...
25
votes
2answers
3k views

$\sum k! = 1! +2! +3! + \cdots + n!$ ,is there a generic formula for this?

I came across a question where I needed to find the sum of the factorials of the first $n$ numbers. So I was wondering if there is any generic formula for this? Like there is a generic formula for ...
14
votes
1answer
1k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
10
votes
3answers
311 views

Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically ...
5
votes
3answers
672 views

Proving that $\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$

I have to prove that: $$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$ I tried to open up the right side with Pascal's definition that: $$ { n \choose k} = {n-1 \choose {k}} + {n-1 ...
4
votes
1answer
120 views

Finite Series - reciprocals of sines

Find the sum of the finite series $$\sum _{k=1}^{k=89} \frac{1}{\sin(k^{\circ})\sin((k+1)^{\circ})}$$ This problem was asked in a test in my school. The answer seems to be ...
4
votes
3answers
782 views

Solve $\sum nx^n$

I am trying to find a closed form solution for $\sum_{n\ge0} nx^n\text{, where }\lvert x \rvert<1$. This solution makes sense to me: $\sum_{n\ge0} x^n=(1-x)^{-1} \\ \frac{d}{d x} \sum_{n\ge0} x^n ...
3
votes
5answers
3k views

calculate sum of square of first n odd numbers

Is there an analytical expression for the summation $$1^2+3^2+5^2+\cdots+(2n-1)^2$$ and how did you derive it?
1
vote
2answers
3k views

How many distinct functions can be defined from set A to B

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are 8^6 distinct functions that can be formed, in other words: |b|^|a| ...
0
votes
3answers
191 views

$1+2+3+4+5+… = -\frac{1}{12}$. Is there any intuition for this? [duplicate]

I was looking into a Numberphile video here. The guy says he was unable to find an intuition. Does there exist one? Is the premise, $1-1+1-1+...=\frac{1}{2}$, reasonable mathematically?
4
votes
1answer
348 views

sum of $\displaystyle \frac{\sin nx }{n^4}$

Consider : $\displaystyle f(x)= \sum_{n=1}^{\infty} \frac{\sin nx }{n^4}$ Find : $\displaystyle \int_0^{x} f(t)\ \mathrm{d}t$.