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

learn more… | top users | synonyms

4
votes
3answers
11k 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| ...
4
votes
4answers
2k views

Proving the sum of the first $n$ natural numbers by induction [duplicate]

I am currently studying proving by induction but I am faced with a problem. I need to solve by induction the following question. $$1+2+3+\ldots+n=\frac{1}{2}n(n+1)$$ for all $n > 1$. Any ...
2
votes
5answers
3k views

Proof by induction that $ \sum_{i=1}^n 3i-2 = \frac{n(3n-1)}{2} $

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: $$ ...
11
votes
3answers
3k views

Combinatorial interpretation of sum of squares, cubes

Consider the sum of the first $n$ integers: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ This has always made the following bit of combinatorial sense to me. Imagine the set ...
15
votes
4answers
866 views

Where do summation formulas come from?

It's a classic problem in an introductory proof course to prove that $\sum_{ i \mathop =1}^ni = \frac{n(n+1)}{2}$ by induction. The problem with induction is that you can't prove what the sum is ...
27
votes
2answers
7k 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 ...
6
votes
3answers
577 views

Summing the series $(-1)^k \frac{(2k)!!}{(2k+1)!!} a^{2k+1}$

How does one sum the series $$ S = a -\frac{2}{3}a^{3} + \frac{2 \cdot 4}{3 \cdot 5} a^{5} - \frac{ 2 \cdot 4 \cdot 6}{ 3 \cdot 5 \cdot 7}a^{7} + \cdots $$ This was asked to me by a high school ...
3
votes
5answers
9k views

Calculate sum of squares 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?
6
votes
3answers
1k views

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

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 ...
6
votes
3answers
3k 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 ...
4
votes
3answers
143 views

How to prove the inequality $2\sqrt{n + 1} − 2 \le 1 +\frac 1 {\sqrt 2}+\frac 1 {\sqrt 3}+ \dots +\frac 1 {\sqrt n} \le 2\sqrt n − 1$?

Prove that for any positive integer $n$, $$2\sqrt{n + 1} − 2 \le 1 +\frac 1 {\sqrt 2}+\frac 1 {\sqrt 3}+ \dots +\frac 1 {\sqrt n} \le 2\sqrt n − 1$$ Progress I think Riemann sum should be used for ...
4
votes
9answers
363 views
3
votes
4answers
9k 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
1answer
76 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 )
12
votes
0answers
626 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 ...
9
votes
3answers
1k 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)
1
vote
2answers
84 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 ...
23
votes
4answers
771 views

Is $\sum_{k=1}^{m-1}\frac{1}{\sin^2\frac{k\pi}{m}}=\frac{m^2-1}{3}$ true for $m\in\mathbb N$?

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 ...
13
votes
3answers
409 views

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

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
30
votes
4answers
2k views

Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$. Challenge: Prove $$\sum_{k=1}^n \left\lfloor \frac{n}{k} ...
28
votes
1answer
762 views

Evaluating the sum $\lim_{n\to \infty}\sqrt[2]{2+\sqrt[3]{2+\sqrt[4]{2+\cdots+\sqrt[n]{2}}}}$

The following nested radical $$\lim_{n\to \infty}\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}$$ is known to converge to 2. We can consider a similar nested radical where the degree of the radicals increases: ...
22
votes
3answers
633 views

A (probably trivial) induction problem: $\sum_2^nk^{-2}\lt1$

So I'm a bit stuck on the following problem I'm attempting to solve. Essentially, I'm required to prove that $\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} < 1$ for all $n$. I've been toiling ...
12
votes
2answers
633 views

Double sum trouble

Evaluate: $$\sum_{j=1}^{\infty} \sum_{i=1}^{\infty} \frac{j^2i}{3^j(j3^i+i3^j)}$$ Honestly, I don't see where to start with this. I am sure that this is a trick question and I am missing something ...
12
votes
10answers
660 views

Show that $ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$

I need a hand in showing that $$ \sum_{n=2}^m \binom{n}{2} = \binom{m+1}{3}$$ Thanks in advance for any help.
12
votes
5answers
2k views

A formula for the power sums: $1^n+2^n+\dotsc +k^n=\,$?

Is there explicit formula for the expression $1^n + 2^n + \dotsc + k^n\,$? I know that for $n=1$ the explicit formula becomes $S=k(k+1)/2$ and for $n=3$ the formula becomes $S^2$. But what about ...
13
votes
5answers
303 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 ...
13
votes
3answers
1k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
11
votes
3answers
4k 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 ...
5
votes
7answers
2k 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 ...
3
votes
1answer
337 views

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

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 ...
2
votes
5answers
156 views

Help with proof using induction: $1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$

I am having trouble with the following proof: For every positive integer $n$: $$1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$$ My work: I have tried to add ...
1
vote
2answers
933 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
204 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 ...
18
votes
3answers
491 views

How prove this sum $\sum_{n=1}^{\infty}\binom{2n}{n}\frac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}$

show that $$\sum_{n=1}^{\infty}\binom{2n}{n}\dfrac{(-1)^{n-1}H_{n+1}}{4^n(n+1)}=5+4\sqrt{2}\left(\log{\dfrac{2\sqrt{2}}{1+\sqrt{2}}}-1\right)$$ where ...
17
votes
5answers
539 views

Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

I found the following formula in a book without any proof: $$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$ I don't know how to prove this at all. Could you show me how ...
12
votes
6answers
967 views

Proving a binomial sum identity

Mathematica tells me that $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$ Although I have not been able to come up with a proof. Proofs, hints, or references are all ...
18
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 ...
4
votes
1answer
140 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 ...
9
votes
2answers
159 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?
5
votes
5answers
1k views

Difficulties in a proof by mathematical induction (involves evaluating $\sum r3^r$).

Please help. I've been stuck on this for 2 days. Haven't found any easy explaining text. The question is: Prove by mathematical induction that : $$ \sum_{r=1}^n r3^r = \frac{3}{4} \left[ 3^n ...
2
votes
1answer
406 views

sum of the product of consecutive legendre symbols is -1

How do I prove the formula $\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}\sum\limits_{a=1}^{p-2} \jaco{a(a+1)}p = -1$ where a varies from 1 to p-2 and p is a prime I got as far as $\jaco{p-a}p = ...
5
votes
1answer
160 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 ...
5
votes
4answers
418 views

Evaluate $\sum_{k=1}^nk\cdot k!$

I discovered that the summation $\displaystyle\sum_{k=1}^n k\cdot k!$ equals $(n+1)!-1$. But I want a proof. Could anyone give me one please? Don't worry if it uses very advanced math, I can just ...
4
votes
6answers
312 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 ...
4
votes
2answers
4k views

Compute $1^2 + 3^2+ 5^2 + \cdots + (2n-1)^2$ by mathematical induction

I am doing mathematical induction. I am stuck with the question below. The left hand side is not getting equal to the right hand side. Please guide me how to do it further. $1^2 + 3^2+ 5^2 + ...
3
votes
3answers
1k views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...
6
votes
1answer
432 views

Integrating $\sum_{n=1}^{\infty} \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$.
3
votes
4answers
489 views

How $\frac{1}{n}\sum_{i=1}^n X_i^2 - \bar X^2 = \frac{\sum_{i=1}^n (X_i - \bar X)^2}{n}$

How $\frac{1}{n}\sum_{i=1}^n X_i^2 - \bar X^2 = \frac{\sum_{i=1}^n (X_i - \bar X)^2}{n}$ i have tried to do that by the following procedure: $\frac{1}{n}\sum_{i=1}^n X_i^2 - \bar X^2$ ...
3
votes
2answers
123 views

Expression for power of a natural number in terms of binomial coefficients

Is there a general expression for the pth power of a natural number k in terms of binomial coefficients? I found this identity in a high-school text, which was obtained by simply equating ...