3
votes
2answers
42 views

Ordered partitions of an integer (with a twist)

I would like to know how to prove (preferably algebraically) that $P_1(2,n)=F_{2n+1}$, where $P_1(2,n)$ is what I define to be the number of ordered partitions of an integer, where the number $1$ has ...
1
vote
1answer
26 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
0
votes
0answers
34 views

Evaluate $S=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$

How to find the value (if possible) of this formula? $$S_{n,m}=\sum_{k=1}^{P}k!\binom{P}{k}\binom{Q}{k}$$ where $P=\min\{m,n\}$ et $Q=\max\{m,n\}$.
0
votes
1answer
42 views

How to calculate the sum of combinatorial numbers

For my work on an almost completely unrelated field I came across the following formula. I know that I have learned that all in high school. But since this is more than 15 years ago in which I never ...
3
votes
2answers
82 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
0
votes
0answers
42 views

An equation on Catalan number [closed]

Catalan numbers have the form $C_n=\frac{1}{n+1}\binom{2n}{n}$ prove: $C_{n+1}=\sum_{m+k=n}C_mC_k$ I tried to expand $C_n$ but soon get confused..
0
votes
0answers
57 views

Showing that two sums are equivalent

given \begin{gather} U_d(x,y,q\mid i_1,\ldots,i_k)=\sum\limits_{n,m\geq0}x^ny^m\sum\limits_{\sigma = i_1\ldots i_k\sigma_{k+1}\ldots\sigma_m\in C_{[d]}(n,m)}q^{v(\sigma)}. \end{gather} show ...
0
votes
0answers
38 views

The sum of palindromes from 100 to 900

I'm working with palindromes from $100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ...
2
votes
1answer
31 views

What is Vandermonde's formula with multisets?

I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$ ...
1
vote
0answers
49 views

Sum of product of binomial coefficients and exponential function

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
0
votes
1answer
96 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
3
votes
2answers
29 views

Find value of $n$ with given conditions

The 4-digit positive number $n$'s digit sum is $20$. The sum of the first two digits is $11$, the sum of the first and the last digit as well. The first digit is the last digit $+3$. What is the ...
4
votes
2answers
73 views

How to evaluate the sum $\sum_{k = 0}^{n}2^k {{n}\choose {k}}$ [duplicate]

How do I evaluate the sum: $$\sum_{k = 0}^{n}2^k {{n}\choose {k}}$$ I know that $2^k = {n \choose 0} + {n \choose 1} + {n \choose 2} + {n \choose 3}... {n \choose k}$, but I don't know how to proceed ...
1
vote
1answer
16 views

Proving an identity involving binomial coefficients and fractions

I've been trying to prove the following formula (for $n > 1$ natural, $a, b$ non-zero reals), but I don't know where to start. $$\sum_{j=1}^n \binom{n-1}{j-1} \left( \frac{a-j+1}{b-n+1} \right) ...
3
votes
4answers
111 views

Proving Combinatorical Summation: $n!=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^n$ [duplicate]

been stuck with this question for the last few hours, any help would be appreciated. $$ {\large n! = \sum_{k = 0}^{n}\left(-1\right)^{k}{\,n\, \choose \,k\,} \left(\,n - k\,\right)^{n}} $$ what I ...
0
votes
3answers
35 views

Sum of combination equilvalence

Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
0
votes
0answers
63 views

What's the interpretation of $\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$?

I'm having problems with finding the combinatorial interpretation of this sum: $$\sum_{i,j} i \cdot j \cdot \binom{2n}{i}\cdot \binom{2n}{j} \cdot \binom{2n}{3n-i-j}$$ Can anyone help, please?
0
votes
0answers
42 views

Gosper summable

I'd like to know why the following is NOT gosper summable: $$\sum_{k\in \Bbb{Z}} \frac{p(k)}{\prod_{j=0}^{m-1}(k+a+j)}$$ where $m>0, m\in\Bbb{Z}$ and $p(k)$ is a polynomial of degree $k=m-1$.
1
vote
2answers
57 views

How to prove this identity [closed]

I would like to prove the following identity without using induction: $$\sum _{ k=1 }^{ n }{ { (-1) }^{ k } {n\choose k} }\cdot k^n=(-1)^n\cdot n!. $$
8
votes
4answers
209 views

Does $\sum_{k=0}^{k=n} {n \choose k} k!$ have a closed form for integers $k,n$?

While doing research in computer system, I came across the following summation: $$S_n = \sum_{k=0}^{n} {n \choose k} k! = \sum_{k=0}^{n} \frac{n!}{(n-k)!}$$ where both $n$ and $k$ are integers. $S_n$ ...
4
votes
1answer
84 views

An inverse binomial summation.

I am looking for a closed form for this summation: $$ \sum_{j=1}^m\frac{r^{-j}}{j{m\choose j}} = \sum_{j=1}^m\frac{r^{-j}}{m{m-1\choose j-1}} = \frac1{rm} \sum_{k=0}^{m-1}\frac{r^{-k}}{{m-1\choose k}} ...
0
votes
0answers
30 views

Simplified formula for the following sum

I have the following sum $$\sum_{n\ge 0}\sum_{0\le \alpha_i\le n+1,\\ \sum_{k=1}^N \alpha_i=n+1} \frac{e^{-(\rho+s)\left(\sum_{k=1}^N \alpha_kT_k\right)}\left(\rho\sum_{k=1}^N ...
3
votes
0answers
107 views

Proving $\sum_{k=1}^{n}\binom{n-1}{k-1}{\binom{n+k}{k}}^{-1}=\frac 12$ combinatorially

Question : How can we prove the following equations combinatorially? $$\begin{eqnarray}\sum_{k=1}^{n}\frac{\binom{n-1}{k-1}}{\binom{n+k}{k}}&=&\frac ...
1
vote
0answers
35 views

Simplifying a sum- combinatorics

Hello fellow mathematicians, I have been working avidly as a high school project to prove Legendre's conjecture. The question below and the other questions I have posted are directly linked to a ...
0
votes
2answers
67 views

Evaluate the sum $\sum_{0\leq j < k\leq n}\binom{n}{j}\binom{n}{k}$

Could someone give me a hint on how to do this? I believe I know what the answer to be (I computed some low values and checked on OEIS). However, I was hoping someone would be able to explain to me ...
1
vote
2answers
75 views

Sum of numbers on chessboard.

Consider the squares of an $8 \times 8$ chessboard filled with the numbers $1,2,3,4 \ldots ,64$ in sequential order. If we choose $8$ squares with the property that there is exactly $1$ from each ...
4
votes
7answers
2k views

I have the pattern: 1 + 2 + 3 + 4 + 5 + 6, but I need the formula for it

I'm writing some software that takes a group of users and compares each user with every other user in the group. I need to display the amount of comparisons needed for a countdown type feature. For ...
0
votes
2answers
25 views

Problem finding explicit function without multiple $\sum$s

For $1≤n \in \mathbb{N}$, I want a function $f$ to have the following value: The sum of all possible products $a_1 * a_2 * ... * a_n$, with $a_i \in \{1, 2, 3, 4\}$ and $a_1 ≤ a_2 ≤ ... ≤ a_n$. For ...
0
votes
1answer
55 views

Show $\large\sum\limits_{j=0}^{r}\binom{j+k-1}{k-1}=\binom{r+k}{k}$

Show $\large\sum\limits_{j=0}^{r}\binom{j+k-1}{k-1}=\binom{r+k}{k}$ Hint: Place $r$ balls in $m$ urns, in how many of this arrangements can you find $b$ balls in the first urn. I'm sure that ...
4
votes
4answers
188 views

How to calculate the following sums?

I would like to know of a way to evaluate the following two for arbitrary $n$. $$\sum_{i=1}^ni!\,, \quad \sum_{i=1}^n \frac{n!}{i!}. $$
4
votes
3answers
204 views

How to closed the sum $\displaystyle \sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$

How to closed the sum $\displaystyle S=\sum_{k=0}^n \dfrac{(-1)^k(2k+1)!!}{(n-k)!k!(k+1)!}$ I'm trying divide two cases $n$ odd and $n$ even. I predict that ...
0
votes
0answers
28 views

Is there an upper limit to the number of times a value can occur in a superset?

Given a set of numbers S=(-5,6,9,3,2,-2,), is there an upper limit to the number of times a particular value (say 4) can occur in the sums of all the combinations of these numbers? For example: in ...
5
votes
0answers
81 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
3
votes
2answers
114 views

Properties of a sequence of sums of binomials

I have encountered the following sequence of alternating sums of binomials and I am wondering whether there is a nicer way to write every element and/or are there some nice properties about it. So, if ...
1
vote
1answer
44 views

Simplifying Sum of Subsets

Given sets $A$ and $R$ such that $R \subseteq A$ and a number $x \leq |A|$, I am trying to simplify the following sum: $$\begin{equation*} \sum_{R \subseteq W \subseteq A : |W| = x} \Big( \sum_{Y ...
0
votes
1answer
20 views

Sum of combinations with a condition

Let $m,n,p,q,r$ be non-negative integers, with $0<m\leq n$ and $p+q+r=n$ The identity $\binom{n}{m}=\sum_{x+y+z=m}\binom{p}{x}*\binom{q}{y}*\binom{r}{z}$ holds? I already checked it for m=2, n=5. ...
1
vote
1answer
43 views

Can this double sum be simplified?

Can this summation be simplified ($A$ is a constant)? $$\displaystyle\sum_{i=1}^{A} \displaystyle\sum_{j>i}^{A} f(i)f(j)$$ By simplified I mean either a closed-form expression in terms of $A$ ...
2
votes
0answers
55 views

How to prove these indentities? [closed]

How to prove these indentities? $\displaystyle \sum \limits_{k\geq0} {2n\choose 2k-1}{k-1\choose m-1}=2^{2n-2m+1}{2n-m\choose m-1}$ $\displaystyle \sum \limits_{k=0}^{m} {m\choose k}{n+k\choose ...
2
votes
1answer
46 views

Calculate sum wtih binomial coefficients

I need help with finding the sum of $\sum \limits_{k=0}^{n} \frac{1}{k+1}{n\choose k}x^{k+1}$
3
votes
1answer
71 views

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $? Does it have a closed form? It's the last piece of a puzzle I need to solve a similar question ...
7
votes
2answers
200 views

How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$ by counting matrices of size $n\times m$ with entries in $\{0,1\}$ ...
6
votes
1answer
109 views

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

I want to prove for any positive integer $n$, the following equation holds: $$\sum_{k=0}^n\frac{1}{n\choose k}=\frac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}{k}$$ I tried to expand $2^k$ as ...
0
votes
2answers
53 views

What is the sum of $1^3q + 2^3q^3 + 3^3q^3 +\cdots+ n^3q^n$?

What is the sum of $1^3*q + 2^3*q^2 + 3^3*q^3 +...+ n^3*q^n ?$
4
votes
5answers
190 views

What is the sum of $1^4 + 2^4 + 3^4+ \dots + n^4$ and the derivation for that expression

What is the sum of $1^4 + 2^4 + 3^4+ \dots + n^4$ and the derivation for that expression using sums $\sum$ and double sums $\sum$$\sum$?
1
vote
3answers
46 views

Using $S_n = \sum_{k=1}^{n}H_k$ where $H_k$ are the harmonic numbers, show $S_n = (n+1)H_n - n$ [duplicate]

The question: Using $S_n = \sum_{k=1}^{n}H_k$ where $H_k$ are the harmonic numbers, show $S_n = (n+1)H_n - n$. So far I have $S_n = \sum_{k=1}^{n} H_k = \sum_{k=1}^{n} ...
6
votes
1answer
257 views

Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

English translation. You can see the original - deprecated - in Portuguese here Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This ...
3
votes
1answer
56 views

On $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$

How do we prove that $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ is an even integer for all $ n \in \mathbb N$ ? (where $\Big[ \space \Big]$ denotes the "greatest integer" function)
12
votes
3answers
199 views

Prove $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Prove that: $$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$ Now, if I simplify the right hand combinatorial expression, it reduces to $\frac{n(n+1)(2n+1)}{6}$ which is well known and can be ...
0
votes
7answers
145 views

Calculating $\binom{1}{2}$

Show $\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to $i!/2!(i-2)!$ and ...
3
votes
2answers
83 views

Simplify a triple sum

I need to find a closed form for this summation: $$\sum_{j=1}^m\sum_{i=j}^m\sum_{k=j}^m\frac{{m\choose i}{{m}\choose{k}}}{j{m\choose j}}r^{k-j+i}$$ I posted this a long time ago, but today I found out ...