Questions tagged [summation]
Questions about evaluating summations, especially finite summations. For infinite series, please consider the (sequences-and-series) tag instead.
2,272
questions
174
votes
8
answers
81k
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{...
- 21.4k
69
votes
18
answers
18k
views
Proof of the hockey stick/Zhu Shijie 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 ...
- 1,530
132
votes
7
answers
65k
views
Values of $\sum_{n=0}^\infty x^n$ and $\sum_{n=0}^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\quad ?
\end{equation*}
Can we generalize the above to
$\displaystyle \sum_{n=...
66
votes
16
answers
47k
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
130
votes
35
answers
287k
views
Proof $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$
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 known as "The sum of the first $n$ positive ...
- 1,467
138
votes
32
answers
75k
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 ...
- 1,733
17
votes
1
answer
9k
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[\...
- 179
82
votes
9
answers
85k
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 = {...
- 821
177
votes
27
answers
17k
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 ...
- 5,445
89
votes
4
answers
10k
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 ...
- 1,422
18
votes
10
answers
15k
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 ...
- 21.4k
174
votes
5
answers
36k
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 $\...
- 5,176
9
votes
9
answers
4k
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
- 203
14
votes
4
answers
4k
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?
- 1,809
13
votes
7
answers
8k
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 ...
- 1,254
11
votes
7
answers
19k
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.
- 3,825
35
votes
12
answers
67k
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)}{...
- 393
21
votes
5
answers
8k
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 ...
- 14.9k
19
votes
5
answers
16k
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 ...
- 936
15
votes
6
answers
4k
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: ...
- 2,209
16
votes
6
answers
9k
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}}$$
...
- 2,327
10
votes
6
answers
813
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 ...
24
votes
4
answers
116k
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} ...
- 361
36
votes
13
answers
6k
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 ...
- 71.8k
34
votes
2
answers
3k
views
Trig sum: $\tan ^21^\circ+\tan ^22^\circ+\cdots+\tan^2 89^\circ = \text{?}$
As the title suggests, I'm trying to find the sum $$\tan^21^\circ+\tan^2 2^\circ+\cdots+\tan^2 89^\circ$$
I'm looking for a solution that doesn't involve complex numbers, or any other advanced branch ...
- 3,065
12
votes
2
answers
12k
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,955
25
votes
3
answers
5k
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, ...
- 4,280
11
votes
3
answers
1k
views
How do you calculate this limit $\lim_{n\to\infty}\sum_{k=1}^{n} \frac{k}{n^2+k^2}$?
How to find the value of $\lim_{n\to\infty}S(n)$, where $S(n)$ is given by $$S(n)=\displaystyle\sum_{k=1}^{n} \dfrac{k}{n^2+k^2}$$
Wolfram alpha is unable to calculate it.
This is a question from a ...
- 5,005
39
votes
5
answers
17k
views
How to find the sum of the series $1+\frac{1}{2}+ \frac{1}{3}+\frac{1}{4}+\dots+\frac{1}{n}$?
How to find the sum of the following series?
$$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n}$$
This is a harmonic progression. So, is the following formula correct?
$\frac{(number ~...
- 9,228
38
votes
4
answers
2k
views
A closed form of $\sum_{k=1}^\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 ...
- 18.9k
10
votes
5
answers
2k
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 ...
- 325
18
votes
7
answers
15k
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:
It ...
- 22k
35
votes
5
answers
8k
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 ...
- 2,976
9
votes
3
answers
1k
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
- 131
44
votes
8
answers
7k
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.
...
- 3,887
33
votes
2
answers
171k
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 ...
- 1,458
30
votes
5
answers
2k
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, ...
- 21.4k
30
votes
7
answers
5k
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 ...
- 1,957
13
votes
8
answers
3k
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$ ...
- 255
23
votes
8
answers
37k
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
$$\...
- 423
3
votes
2
answers
3k
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^{...
- 453
94
votes
4
answers
95k
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 ...
- 1,131
31
votes
7
answers
12k
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 ...
- 116k
1
vote
8
answers
505
views
Prove 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 ...
- 400
69
votes
3
answers
98k
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 the ...
- 2,523
16
votes
2
answers
5k
views
Finite Sum of Power?
Can someone tell me how to get a closed form for
$$\sum_{k=1}^n k^p$$
For $p = 1$, it's just the classic $\frac{n(n+1)}2$.
What is it for $p > 1$?
- 2,422
13
votes
3
answers
27k
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 ...
- 547
3
votes
2
answers
4k
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 ...
- 33
50
votes
8
answers
4k
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 ...
- 122k
4
votes
5
answers
6k
views
Sum with binomial coefficients: $\sum_{k=0}^{n}{2n\choose 2k}$ [closed]
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}$?
- 1,403