Skip to main content

All Questions

Filter by
Sorted by
Tagged with
4 votes
0 answers
235 views

A combinatorial proof for equality of two $q$-series

Consider the following two $q$-series \begin{align*} f(q):&=\sum_{k=1}^{\infty} \frac{(-1)^{k-1}(1 + q^k)\,q^{\binom{k + 1}2}}{(1 - q^k)^2} \qquad \text{and} \\ g(q):&=\frac1{\prod_{j=1}^{\...
1 vote
1 answer
117 views

Product/quotient of factorials beget dyadic powers

I am writing up some notes and the following occurred to me and I would like to see if there are a variety of ways to prove it. Just for reference, the identity pops out of equality between constant ...
24 votes
2 answers
3k views

A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. That is, Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...
2 votes
1 answer
377 views

Prove positivity of rational functions

We say a rational function $F(z)$ is positive if the coefficients of its Maclaurin expansion, in the variable $z$, are non-negative. In this context, let $$F_r(z):=\frac{1 - 2z + z^r - (1 - z)^r}{(1 - ...
16 votes
6 answers
2k views

Alternative proofs sought after for a certain identity

Here is an identity for which I outlined two different arguments. I'm collecting further alternative proofs, so QUESTION. can you provide another verification for the problem below? Problem. Prove ...
1 vote
1 answer
183 views

A binomial convolution of Catalan numbers vs "utterly odd numbers"

An integer is called utterly odd if the terminal string of $1$’s in its binary representation has odd length. A number $2^{k+1}m+(2^k-1)$ where $m\geq0$ (every non-negative integer has this form) is ...
2 votes
0 answers
147 views

Asking for a combinatorial proof of a binomial-sum

QUESTION. Is there a combinatorial proof of the below identity? $$\sum_{k=0}^{n-1}\frac{2^{2k}}{2k+1}\frac{\binom{2n}n}{\binom{2k}k}=2^{2n}-\binom{2n}n.$$ REMARK. There are many other proofs (...
3 votes
2 answers
244 views

Is there a combinatorial reason for variable-independence of this binomial-coefficient identity?

Consider the following identity $$\sum_{n=0}^{R-t}\binom{n+\ell}n\binom{R-\ell-n}{R-t-n}=\binom{R+1}{t+1}.\tag1$$ It is relatively easy to give an algebraic or mechanical proof of (1). But, I like to ...
8 votes
2 answers
274 views

A link between hooks, contents and parts of a partition

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Denote its conjugate partition by $\lambda'$. For example, if $\lambda=(4,3,1)$ then $\lambda'=(3,2,2,1)$. ...
6 votes
5 answers
944 views

Combinatorial proof of Catalan's identity

Consider the problem of tiling a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$, Let's denote $f_n$ to be the number of ways to tile this so-called ($n$)-board.Then $f_n=F_{...
2 votes
0 answers
109 views

Average number of pieces of a random piecewise-linear function

Let $I$ be a (nonempty) compact interval in $\mathbb R$ and $a_1,b_1,\ldots,a_L,b_L \in \mathbb R$. Let $\varphi$ be a piecewise function with $T \ge 2$ pieces(for example $T=2$ for the choice $\...
2 votes
0 answers
58 views

Bounds for $\sum_{t=1}^Tn_t(s_t)^{-\alpha}\mu(s_t)$ where $n_t(s) = \sum_{1 \le t' \le t} 1_{\{s_{t'}=s\}}$ for $s \in [k]$ and $\mu \in \Delta_k$

Disclaimer: I'm not certain this is the right venue for this post, but I'll give it a try... So trying prove some bounds in my ongoing work in theoretical reinforcement learning, I encountered the ...
6 votes
2 answers
1k views

Products and sum of cubes in Fibonacci

Consider the familiar sequence of Fibonacci numbers: $F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}$. Although it is rather easy to furnish an algebraic verification of the below identity, I wish to see a ...
8 votes
1 answer
493 views

Generating function for $3$-core partitions

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$. We call $\lambda$ a $t$-core partition if none of ...
4 votes
2 answers
449 views

Prove that there exists a nonempty subset $ I$ of $ \{1,2,...,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer

Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...
2 votes
1 answer
83 views

On submatrices: size bound

Let $M$ be a generic $2n\times 2n$ matrix and fix $k\leq n$. Suppose $\mathcal{F}$ is a family of submatrices under the conditions that $A\in\mathcal{F}$ provided (a) $A$ is a $k\times k$ ...
3 votes
1 answer
329 views

Generating function for 3 -core partitions: Part II

Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Further, let $h_u$ denote the hook-length of the cell $u$. We call $\lambda$ a $t$-core partition if none of ...
8 votes
2 answers
325 views

A link between hooks and contents: Part II

This is a question in the spirit of an earlier problem. Let $\lambda$ be an integer partition: $\lambda=(\lambda_1\geq\lambda_2\geq\dots\geq0)$. Recall also the notation for the content of a cell $...
20 votes
1 answer
1k views

A proof required for this identity [duplicate]

Experiments support the below identity. Question. Is this true? Combinatorial proof preferred if possible. $$\sum_{m=0}^n\binom{n-\frac13}m\binom{n+\frac13}{n-m}(1+6m-3n)^{2n+1} =\left(\frac43\...
3 votes
1 answer
334 views

Simplifying a double sum of inverses

Let $$f(n) = 2 \sum\limits_{a = 2}^{n - 1} \sum\limits_{b = n + 1}^{n + a - 1}\frac{1}{ab} .$$ One can see that $$\lim\limits_{n \to \infty}f(n) = 2\int\limits_0^1 \frac{dx}{x} \int\limits_1^{1 + x}\...
8 votes
1 answer
486 views

Prove that these are polynomials

Define the functions $$F_n(q)=\frac1{(1-q)^{2n}}\sum_{k=0}^n(-q)^k\frac{2k+1}{n+k+1}\binom{2n}{n-k} \prod_{j=0,\,j\neq k}^n\frac{1+q^{2j+1}}{1+q}.$$ The numbers $\frac{2k+1}{n+k+1}\binom{2n}{n-k}$ ...
2 votes
2 answers
452 views

These polynomials are always either even or odd [duplicate]

The falling factorials are $(x)_n=x(x-1)\cdots(x-n+1)$ with $(x)_0:=1$. Define the forward shift $E$ and the discrete derivative $\delta=E-1$, respectively, by $$Ef(x)=f(x+1) \qquad \text{and} \qquad \...
3 votes
1 answer
200 views

On decompositions of integers as a linear combination of $(1, 2, 3,\ldots)$

Edited: Given integer $N\geq 0$, let $$I(N):=\Bigl\{(n_k)_{k\geq 1}\in {\mathbb N}^\infty \,:\, n_k\geq 0, \sum_{k\geq 1}kn_k = N \Bigr\}$$ be the set of all decompositions of $N$ as a linear ...
1 vote
0 answers
118 views

Carry operations when adding two numbers [closed]

Let $x$ be a large positive real number and let $q\leq 2$ be a positive integer. It is known that for a positive integer $n,$ there exists a unique sequence $\left\{0\leq n_k\leq q-1\right\}_{k\geq 0}$...
5 votes
4 answers
1k views

Binomial ID $\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}$

Could I get some help with proving this identity? $$\sum_{k=m}^p(-1)^{k+m}\binom{k}{m}\binom{n+p+1}{n+k+1}=\binom{n+p-m}{n}.$$ It has been checked in Matlab for various small $n,m$ and $p$. I have a ...
1 vote
1 answer
218 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\...