Questions tagged [summation]
Questions about evaluating summations, especially finite summations. For infinite series, please consider the (sequences-and-series) tag instead.
128
votes
5answers
41k views
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression?
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression? For example here is the sum of $\cos$ series:
$$\sum_{k=0}^{n-1}\cos (a+k \cdot d) =\frac{\sin(n \times \frac{...
57
votes
12answers
32k 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
111
votes
5answers
28k views
Value of $\sum\limits_n x^n$
Why does the following hold:
\begin{equation*}
\displaystyle \sum\limits_{n=0}^{\infty} 0.7^n=\frac{1}{1-0.7} = 10/3 ?
\end{equation*}
Can we generalize the above to
$\displaystyle \sum_{n=0}^{\...
83
votes
30answers
164k 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?
PS: This problem is know as "The sum of the first $n$ positive ...
44
votes
13answers
8k views
Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's the name of this identity? Is it the identity of the Pascal's triangle ...
11
votes
1answer
6k views
$\sum \cos$ when angles are in arithmetic progression [duplicate]
Possible Duplicate:
How can we sum up $\sin$ and $\cos$ series when the angles are in arithmetic progression?
Prove $$\cos(\alpha) + \cos(\alpha + \beta) + \cos(\alpha + 2\beta) + \dots + \cos[\...
113
votes
31answers
57k views
Sum of First $n$ Squares Equals $\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 ...
149
votes
23answers
12k views
Proving the identity $\sum_{k=1}^n {k^3} = \big(\sum_{k=1}^n k\big)^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 interpretation ...
60
votes
6answers
45k views
Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$
I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.
I already know the logical Proof:
$${n \choose k}^2 = {...
11
votes
4answers
2k views
Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity) [duplicate]
Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity
$$
\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}
$$
holds?
7
votes
9answers
2k 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
17
votes
10answers
8k 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 ...
93
votes
5answers
22k 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 $\...
66
votes
4answers
6k views
Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
It's not difficult to show that
$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$
On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
9
votes
7answers
5k views
Alternating sum of binomial coefficients: given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$
Let $n$ be a positive integer. Prove that
\begin{align}
\sum_{k=0}^n \left(-1\right)^k \binom{n}{k} = 0 .
\end{align}
I tried to solve it using induction, but that got me nowhere. I think the ...
31
votes
12answers
22k views
Why $\sum_{k=1}^{\infty} \frac{k}{2^k} = 2$? [duplicate]
Can you please explain why
$$
\sum_{k=1}^{\infty} \dfrac{k}{2^k} =
\dfrac{1}{2} +\dfrac{ 2}{4} + \dfrac{3}{8}+ \dfrac{4}{16} +\dfrac{5}{32} + \dots =
2
$$
I know $1 + 2 + 3 + ... + n = \dfrac{n(n+1)}{...
20
votes
5answers
5k 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 ...
34
votes
5answers
10k 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 :
$\frac{(...
32
votes
4answers
2k views
A closed form of $\sum_{k=0}^\infty\frac{(-1)^{k+1}}{k!}\Gamma^2\left(\frac{k}{2}\right)$
I am looking for a closed form of the following series
\begin{equation}
\mathcal{I}=\sum_{k=1}^\infty\frac{(-1)^{k+1}}{k!}\Gamma^2\left(\frac{k}{2}\right)
\end{equation}
I have no idea how to ...
8
votes
4answers
574 views
Proving Binomial Identity without calculus
How to establish the following identities without the help of calculus:
For positive integer $n, $
$$\sum_{1\le r\le n}\frac{(-1)^{r-1}\binom nr}r=\sum_{1\le r\le n}\frac1r $$
and $$\sum_{0\le r\le ...
6
votes
3answers
896 views
Evaluating Combination Sum $\sum{n+k\choose 2k} 2^{n-k}$
Evaluate $$\sum_{k=0}^n{n+k\choose 2k} 2^{n-k}$$
So im not really sure how to begin with this. I would imagine we start with dividing out $2^{n}$, but not really sure much past that
13
votes
6answers
6k 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}}$$
...
38
votes
8answers
4k 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.
...
11
votes
6answers
2k views
Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?
The successive difference of powers of integers leads to factorial of that power. Here's the formula:
$$\sum_{r=0}^{n}\binom{n}{r}(-1)^r(n-r)^n=n!$$
Can anyone give a proof of this result?
Note: ...
20
votes
7answers
6k views
Floor function properties: $[2x] = [x] + [ x + \frac12 ]$ and $[nx] = \sum_{k = 0}^{n - 1} [ x + \frac{k}{n} ] $
I'm doing some exercises on Apostol's calculus, on the floor function. Now, he doesn't give an explicit definition of $[x]$, so I'm going with this one:
DEFINITION Given $x\in \Bbb R$, the integer ...
7
votes
4answers
1k views
What is the formula for $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\cdots +\frac{1}{n(n+1)}$
How can I find the formula for the following equation?
$$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\cdots +\frac{1}{n(n+1)}$$
More importantly, how would you approach finding the ...
29
votes
2answers
1k views
Trig sum: $\tan ^21^\circ+\tan ^22^\circ+…+\tan^2 89^\circ = ?$
As the title suggests, I'm trying to find the sum $$\tan^21^\circ+\tan^2 2^\circ+...+\tan^2 89^\circ$$
I'm looking for a solution that doesn't involve complex numbers, or any other advanced branch in ...
6
votes
6answers
9k views
How to prove Vandermonde's Identity: $\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}$?
How can we prove that
$$\sum_{k=0}^{n}\binom{R}{k}\binom{M}{n-k}=\binom{R+M}{n}?$$
(Presumptive) Source: Theoretical Exercise 8, Ch 1, A First Course in Probability, 8th ed by Sheldon Ross.
57
votes
4answers
44k views
What is the term for a factorial type operation, but with summation instead of products? [duplicate]
(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 ...
25
votes
2answers
127k 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 of ...
11
votes
4answers
9k 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:
...
24
votes
4answers
1k views
How to prove $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$?
Other than the general inductive method,how could we show that $$\sum_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$$
Apart from induction, I tried with Wolfram Alpha to check the validity, ...
9
votes
5answers
10k views
How to show that this binomial sum satisfies the Fibonacci relation?
The binomial sum
$$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$
satisfies the Fibonacci relation.
I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints ...
23
votes
3answers
4k views
Does uncountable summation, with a finite sum, ever occur in mathematics?
Obviously, “most” of the terms must cancel out with opposite algebraic sign.
You can contrive examples such as the sum of the members of R being 0, but does an uncountable sum, with a finite sum, ...
3
votes
2answers
3k 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 ...
2
votes
2answers
2k views
Proving the geometric sum formula by induction
$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$
I want to prove this by induction. Here's what I have.
$$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$
I wanted to factor a $q^{...
27
votes
13answers
3k views
Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula
As far as every question I've seen concerning "what is $\sum_{k=1}^nk^p$" is always answered with "Faulhaber's formula" and that is just about the only answer. In an attempt to make more interesting ...
14
votes
2answers
4k views
Finite Sum of Power?
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 $\frac{n(n+1)}2$.
What is it for $x > 1$?
24
votes
7answers
2k 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 ...
12
votes
8answers
2k views
I found this odd relationship, $x^2 = \sum_\limits{k = 0}^{x-1} (2k + 1)$. [duplicate]
I stumbled across this relationship while I was messing around. What's the proof, and how do I understand it intuitively? It doesn't really make sense to me that the sum of odd numbers up to $2x + 1$ ...
19
votes
8answers
13k views
Proving $\sum_{k=0}^n(-1)^k\binom nk=0$
Show that
$$\sum_{k=0}^n(-1)^k\binom nk=0$$
So for odd $n$ we have an even number of terms. So $\binom nk=\binom n{n-k}$ which have opposite signs. Thus the sum is 0.
For even $n$ we have that
$$\...
12
votes
2answers
8k 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 ...
11
votes
2answers
53k views
Proving by induction that $ \sum_{k=0}^n{n \choose k} = 2^n$
Prove by induction that for all $n \ge 0$:
$${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$
In the inductive step, use Pascal’s identity, which is:
$${n+1 \choose k} = {n \choose k-1} ...
54
votes
3answers
53k 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 ...
28
votes
5answers
6k views
use of $\sum $ for uncountable indexing set
I was wondering whether it makes sense to use the $\sum $ notation for uncountable indexing sets. For example it seems to me it would not make sense to say
$$
\sum_{a \in A} a \quad \text{where A is ...
1
vote
7answers
276 views
Proof that $\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2$
If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$\left(\sum^n_{k=1}x_k\right)\left(\sum^n_{k=1}y_k\right)\geq n^2.$$
I've been learning induction, and I've come across this ...
4
votes
5answers
2k views
Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$
I'm repeating material for test and I came across the example that I can not do. How to calculate this sum:
$\displaystyle\sum_{k=0}^{n}{2n\choose 2k}$?
4
votes
2answers
342 views
Find $\sum_{k=1}^{\infty}\frac{1}{2^{k+1}-1}$
Calculate $$\sum_{k=1}^{\infty}\frac{1}{2^{k+1}-1}.$$
I used Wolfram|Alpha to compute it and got it to be approximately equal to $0.6$. How to compute it? Can someone give me a hint or a suggestion ...
302
votes
8answers
30k views
The length of toilet roll
Fun with Math time.
My mom gave me a roll of toilet paper to put it in the bathroom, and looking at it I immediately wondered about this: is it possible, through very simple math, to calculate (with ...
37
votes
6answers
2k views
Finite Sum $\sum\limits_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}$
Question : Is the following true for any $m\in\mathbb N$?
$$\begin{align}\sum_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}=\frac{m^2-1}{3}\qquad(\star)\end{align}$$
Motivation : I reached $(\star)$ by ...
