Questions tagged [summation]

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

Filter by
Sorted by
Tagged with
6
votes
4answers
1k views

How to prove that $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$ [duplicate]

I know that $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$ but I cannot find a way how to prove it. I tried induction but it did not work. On wiki they say that I should use differentiation but I do ...
4
votes
6answers
6k views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
4
votes
6answers
2k views

Evaluating even binomial coefficients

Can someone give me a hint how to evaluate $$ \binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{o(n)},$$ where $o(n)$ is $n$ if $n$ is even and $n-1$ otherwise ?
3
votes
1answer
811 views

Evaluate $\sum_{k = 0}^{n} {n\choose k} k^m$ [duplicate]

So, I wonder what is the evaluation of $$\sum_{k = 0}^{n} {n\choose k} k^m\text{,}\qquad (*)$$ where $m,n\in \mathbb{N}$. One of my tries: knowing that $$k^m = \sum_{j = 0}^{m}\text{S}(m,j)\cdot k(k-...
2
votes
1answer
545 views

Is there a general product formula for $\sum\limits_{k=1}^{n} k^p$ [duplicate]

I'm familiar with Faulhaber's formula to express this sum as a much simpler one, but it appears that for any $p$ there's a product formula in $n$ for the sum e.g.: $$\begin{align} & \sum\limits_{...
0
votes
1answer
105 views

Summation of binomial coefficients [duplicate]

Is there a closed formula for: $\sum_{i=1}^{N}{\binom{i+k}{i}}$ ( k is a constant whole number )
7
votes
1answer
156 views

Calculating $\sum_{k=1}^nk(k!)$ combinatorially [duplicate]

The sum $\sum_{k=1}^nk(k!)$ can be easily calculated by noting $k(k!)=(k+1)!-k!$. Is there a way to calculate the sum nicely using a combinatorial argument. Is it possible to notice it is $(n+1)!-1$ ...
3
votes
3answers
151 views

Proof of $\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n}$ [duplicate]

Prove that for $n\geq 2, \: \sum_{k = 1}^{n} \frac{1}{k^{2}} < 2 - \frac{1}{n} $ I used induction and I compared the LHS and the RHS but I'm getting an incorrect inequality
3
votes
4answers
787 views

Formula for $\sum_{k=1}^n \frac{1}{k(k+1)(k+2)}$?

I was trying to find a formula for the series $$\sum_{k=1}^n \frac{1}{k(k+1)(k+2)} =? $$ I tried to break this into partial fractions...To see if I could telescope this series.. The partial ...
2
votes
4answers
638 views

For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$. I don't quite know how to approach this problem. Can someone help and ...
2
votes
3answers
2k views

Partial Sums of Geometric Series

This may be a simple question, but I was slightly confused. I was looking at the second line $S_n(x)=1-x^{n+1}/(1-x)$. I was confused how they derived this. I know the infinite sum of a geometric ...
-3
votes
2answers
2k views

Proving $\sum_{k=1}^n\frac1{\sqrt k}<2\sqrt n$ by induction [closed]

I am just starting out learning mathematical induction and I got this homework question to prove with induction but I am not managing. $$\sum_{k=1}^n\frac1{\sqrt k}<2\sqrt n$$ Please help!
100
votes
24answers
15k views

Can an infinite sum of irrational numbers be rational?

Let $S = \sum_ {k=1}^\infty a_k $ where each $a_k$ is positive and irrational. Is it possible for $S$ to be rational, considering the additional restriction that none of the $a_k$'s is a linear ...
50
votes
6answers
2k views

Generalizing the sum of consecutive cubes $\sum_{k=1}^n k^3 = \Big(\sum_{k=1}^n k\Big)^2$ to other odd powers

We have, $$\sum_{k=1}^n k^3 = \Big(\sum_{k=1}^n k\Big)^2$$ $$2\sum_{k=1}^n k^5 = -\Big(\sum_{k=1}^n k\Big)^2+3\Big(\sum_{k=1}^n k^2\Big)^2$$ $$2\sum_{k=1}^n k^7 = \Big(\sum_{k=1}^n k\Big)^2-3\Big(\...
18
votes
5answers
19k views

How to change the order of summation?

I have stumbled upon, multiple times, on cases where I need to change the order of summation (usally of finite sums). One problem I saw was simple $$ \sum_{i=1}^{\infty}\sum_{j=i}^{\infty}f(i,j)=\...
17
votes
4answers
566 views

How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $

Show that $$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$ I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you
20
votes
5answers
1k views

Prove $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$ [duplicate]

In reading about A polarization identity for multilinear maps by Erik G F Thomas, I am led to prove the following combinatorial identity, which I cannot find anywhere, nor do I have any idea how to ...
10
votes
5answers
498 views

Prove: ${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-…(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}$

Prove: $${n\choose 0}-\frac{1}{3}{n\choose 1}+\frac{1}{5}{n\choose 2}-...+(-1)^n\frac{1}{2n+1}{n\choose n}=\frac{n!2^n}{(2n+1)!!}.$$ Here, $(2n+1)!!$ is an "odd factorial": $(2n+1)!! = 1 \cdot 3 \...
7
votes
4answers
321 views

Proof of the summation $n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$?

$$n!=\sum_{k=0}^n \binom{n}{k}(n-k+1)^n(-1)^k$$ Could anyone give the proof of the above equation? Thanks in advance!
14
votes
5answers
250 views

How to evaluate the sum $\sum_{n=1}^{\infty}\frac{1}{(2n+1)(2n+2)}\left(1+\frac{1}{2}+…+\frac{1}{n}\right)$

How to evaluate the sum: $$S=\sum_{n=1}^{\infty}\frac{1}{(2n+1)(2n+2)}\left(1+\frac{1}{2}+...+\frac{1}{n}\right)$$ Can anyone help me,I really appreciate it.
10
votes
2answers
4k views

Easy way of memorizing or quickly deriving summation formulas

My math professor recently told us that she wants us to be familiar with summation notation. She says we have to have it mastered because we are starting integration next week. She gave us a bunch of ...
23
votes
1answer
3k 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 ...
12
votes
4answers
2k views

Prove that $1<\frac{1}{1001}+\frac{1}{1002}+\frac{1}{1003}+\ldots+\frac{1}{3001}<\frac43$

Prove that $$1<\dfrac{1}{1001}+\dfrac{1}{1002}+\dfrac{1}{1003}+\ldots+\dfrac{1}{3001}<\dfrac43 \, .$$ My work: $$\begin{eqnarray*} S&=&\bigg(\dfrac{1}{1001}+\dfrac{1}{3001}\bigg)+\...
17
votes
5answers
758 views

Evaluate the limit $\lim\limits_{n \to \infty} \frac{1}{1+n^2} +\frac{2}{2+n^2}+ \ldots +\frac{n}{n+n^2}$

Evaluate the limit $$\lim_{n \to \infty} \dfrac{1}{1+n^2} +\dfrac{2}{2+n^2}+ \ldots+\dfrac{n}{n+n^2}$$ My approach : If I divide numerator and denominator by $n^2$ I get : $$\lim_{ n \to \...
6
votes
7answers
3k views

Binomial Coefficients Proof: $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$.

Prove that $\sum_{k=0}^n {n \choose k} ^{2} = {2n \choose n}$. I am trying to prove this by induction. I am having some difficulty after the induction step. Here is what I have so far: I start with ...
5
votes
3answers
570 views

Cotangent summation (proof)

How to sum up this thing, i tried it with complex number getting nowhere so please help me with this,$$\sum_{k=0}^{n-1}\cot\left(x+\frac{k\pi}{n}\right)=n\cot(nx)$$
12
votes
4answers
5k views

Computig the series $\sum\limits_{n=2}^\infty \ln\left(1-\frac{1}{n^2}\right)$

So I have this problem for midterm reviews: $$\sum_{n=2}^\infty \ln\left(1-\frac{1}{n^2}\right)=\text{ ?}$$ I know that you can find the series form of a natural log, as shown here: $$\ln\left(1-\...
11
votes
2answers
462 views

A Ramanujan-type identity: $11\sum_{n=1}^{\infty}\frac{n^3}{e^{2n\pi}-1}-16\sum_{n=1}^{\infty}\frac{n^3}{e^{4n\pi}-1}=\frac{1}{48}$

Out of curiosity, why it is these sums yield a rational answer? $$11\sum_{n=1}^{\infty}\frac{n^3}{e^{2n\pi}-1}-16\sum_{n=1}^{\infty}\frac{n^3}{e^{4n\pi}-1}=\frac{1}{48}$$ I found this identity ...
11
votes
2answers
351 views

How find this Fibonacci sequence sum $\sum_{k=0}^{\infty}\frac{1}{F_{2^k}}$

let sequence $\{F_{n}\}$ such $$F_{1}=1,F_{2}=1,F_{m+1}=F_{m}+F_{m-1},m\ge 2$$ Find this value $$I=\sum_{k=0}^{\infty}\dfrac{1}{F_{2^k}}$$ My try: I know this $$F_{n}=\dfrac{1}{\sqrt{5}}\...
11
votes
6answers
10k views

Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $

[Corrected question] I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $$ I would like to see a combinatorical (logical) solution, ...
9
votes
4answers
2k views

Show that $\sum_{k=0}^n\binom{3n}{3k}=\frac{8^n+2(-1)^n}{3}$

The other day a friend of mine showed me this sum: $\sum_{k=0}^n\binom{3n}{3k}$. To find the explicit formula I plugged it into mathematica and got $\frac{8^n+2(-1)^n}{3}$. I am curious as to how one ...
9
votes
4answers
123k views

Prove that $1^3 + 2^3 + … + n^3 = (1+ 2 + … + n)^2$ [duplicate]

This is what I've been able to do: Base case: $n = 1$ $L.H.S: 1^3 = 1$ $R.H.S: (1)^2 = 1$ Therefore it's true for $n = 1$. I.H.: Assume that, for some $k \in \Bbb N$, $1^3 + 2^3 + ... + k^3 = (1 +...
8
votes
2answers
613 views

Prove that $\frac{1}{4-\sec^{2}(2\pi/7)} + \frac{1}{4-\sec^{2}(4\pi/7)} + \frac{1}{4-\sec^{2}(6\pi/7)} = 1$

How can I prove the fact $$\frac{1}{4-\sec^{2}\frac{2\pi}{7}} + \frac{1}{4-\sec^{2}\frac{4\pi}{7}} + \frac{1}{4-\sec^{2}\frac{6\pi}{7}} = 1.$$ When asked somebody told me to use the ideas of ...
11
votes
9answers
398 views

How to compute $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to ...
8
votes
2answers
327 views

Using right-hand Riemann sum to evaluate the limit of $ \frac{n}{n^2+1}+ \cdots+\frac{n}{n^2+n^2}$

I'm asked to prove that $$\lim_{n \to \infty}\left(\frac{n}{n^2+1}+\frac{n}{n^2+4}+\frac{n}{n^2+9}+\cdots+\frac{n}{n^2+n^2}\right)=\frac{\pi}{4}$$ This looks like it can be solved with Riemann sums, ...
4
votes
1answer
88 views

proving $\left(1+\frac 1n\right)^{n} = 1 + \sum_{k=1}^n \{\frac 1{k!}\prod_{r=0}^{k-1}(1-\frac rn)\}$ using the binomial theorem

$$\left(1+\frac 1n\right)^{n} = 1 + \sum\limits_{k=1}^n \left\{\frac 1{k!}\prod_{r=0}^{k-1}\left(1-\frac rn\right)\right\}$$ this exercise is taken from Apostol's Calculus I (page 45) and it's ...
9
votes
2answers
10k views

What is the derivative of a summation with respect to its upper limit?

For the moment, consider the corresponding problem involving integration. Let $s(x)$ be the explicit solution to the following integral. $ \displaystyle s(x)=\int_a^x f(t) \, dt $ The function $s'(x)...
9
votes
2answers
237 views

Summation of series $\sum_{k=0}^\infty 2^k/\binom{2k+1}{k}$

How to find the sum of this series? $$\sum_{k=0}^{\infty}\cfrac{{2}^{k}}{\binom{2k+1}{k}}$$ It seems very easy. But I still can not work it out, can anyone help?
8
votes
3answers
1k views

Formula for $1^k+2^k+3^k…n^k$ for $n,k \in \mathbb{N}$

So I've been looking for a formula where I can input the parameter $k$ and it will give me a formula for $1^k+2^k+3^k...+ n^k$ with $n,k \in \mathbb{N}$. The result is always a polynomial with $k+1$ ...
5
votes
2answers
1k views

Euler-Maclaurin summation for $e^{-x^2}$

I want to approximate the sum $$\sum_{k=0}^\infty e^{-k^2}$$ using the Euler-Maclaurin formula $$\sum_{k=0}^\infty f(k) = \int_0^\infty f(x) \, dx + \frac{1}{2}(f(0) + f(\infty)) + \frac{1}{12}(f'(\...
3
votes
2answers
342 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
16
votes
2answers
623 views

proof of $\sum\nolimits_{i = 1}^{n } {\prod\nolimits_{\substack{j = 1\\j \ne i}}^{n } {\frac{{x_i }}{{x_i - x_j }}} } = 1$ [duplicate]

i found a equation that holds for any natural number of n and any $x_i \ne x_j$ as follows: $$\sum\limits_{i = 1}^{n } {\prod\limits_{\substack{j = 1\\j \ne i}}^{n } {\frac{{x_i }}{{x_i - x_j }}} } ...
13
votes
5answers
501 views

Proof that $\sum_{1}^{\infty} \frac{1}{n^2} <2$

I know how to prove that $$\sum_1^{\infty} \frac{1}{n^2}<2$$ because $$\sum_1^{\infty} \frac{1}{n^2}=\frac{\pi^2}{6}<2$$ But I wanted to prove it using only inequalities. Is there a way to do ...
10
votes
2answers
1k views

Alternative combinatorial proof for $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$

I have a question with regards to combinatorics. I am supposed to show the following combinatorial identity: $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^...
10
votes
8answers
729 views

Telescoping series of form $\sum (n+1)\cdots(n+k)$ [duplicate]

Wolfram Alpha is able to telescope sums of the form $\sum (n+1)\cdots(n+k)$ e.g. $(1\cdot2\cdot3) + (2\cdot3\cdot4) + \cdots + n(n+1)(n+2)$ How does it do it? EDIT: We can rewrite as: $\sum {(n+k)!...
9
votes
4answers
1k views

Orthogonality for Binomial Coefficients

Could somebody explain to me where these two formulas come from as applications of the binomial theorem? $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ for non-negative integers $r\lt n$. And $$\sum_{k=0}^...
6
votes
4answers
175 views

Prove that $1<\frac{1}{n+1}+\frac{1}{n+2}+…+\frac{1}{3n+1}$

Prove that $1<\dfrac{1}{n+1}+\dfrac{1}{n+2}+...+\dfrac{1}{3n+1}$. By using the Mathematical induction. Suppose the statement holds for $n=k$. Then for $n=k+1$. We have $\dfrac{1}{k+2}+\dfrac{1}{k+...
6
votes
6answers
3k views

Evaluating $\lim_{n\to\infty} \frac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}}$ using integral

Evaluate $\lim\limits_{n\to\infty} \dfrac{1^{99} + 2^{99} + \cdots + n^{99}}{n^{100}}$ This is the question I remembered from my high school textbook (I remembered it while reading about something ...
6
votes
2answers
222 views

Showing that $\sum_{i=1}^n \frac{1}{i} \geq \log{n}$

I have been trying to prove this by induction on $n\in \mathbb{N}$, but this approach seemed to get me nowhere. I have a suspicion it might be necessary to express $\log{n}$ as $\int_1^n 1/x\text{ }dx$...
6
votes
4answers
7k views

Evaluating a summation of inverse squares over odd indices

$$ \sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}$$ I want to evaluate this sum when $n$ takes only odd values.