All Questions
Tagged with binomial-coefficients polynomials
188
questions
3
votes
5
answers
218
views
Coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
Find the coefficient of $x^{21}$ in $(1+x+x^2+\dots+x^{10})^4$
I tried splitting the terms inside the bracket into two parts $1+x+\dots+x^9$ and $x^{10}$, and then tried binomial theorem, but that ...
2
votes
1
answer
108
views
Find all values of $n$ where $2n^2+7n+3$ is prime. [closed]
Problem: Find all values of $n$ where $2n^2+7n+3$ is prime.
What I know:
All prime numbers are only divided by one and themselves.
To reach a solution, I need to factor the polynomial and equal the ...
2
votes
0
answers
77
views
Closed expression for a combinatorial sum
The following equality is true for every positive integer $n$ :
$$\sum_{k=0}^n {n \choose k} = 2^n $$
It is a special case ($p = 0$) of the sequence :
$$S_{p, n}=\sum_{k=0}^n k^p {n \choose k} $$
For ...
2
votes
1
answer
342
views
Polynomial representation of $\sum\limits_{n=m+1}^N \binom {n-1} m$
Background: I am looking for a polynomial representation of
$$
\sum_{n=m+1}^N \binom {n-1} m \tag{1}
$$
where $m\in\mathbb{Z^+}$ is a positive integer $2,3,4,\ldots $ that is greater than or equal to $...
1
vote
2
answers
120
views
Coefficient of polynomial of $x^k$
Consider a polynomial of power n:
$P(x)=1+x+x^2+\dots+x^n$
How do I find coefficient of $x^k$, where $0\le k\le 3n$ of the polynomial $P^3(x)$?
I have tried plugging in different values of $n$ to find ...
0
votes
0
answers
40
views
Finding particular solution using domain transformation
$$ φ(n)=5 φ\left(\frac{n}{2}\right)-6 φ\left(\frac{n}{4}\right)+n $$ where $$ \varphi (1) = 2 \\ \text{and} \\ \varphi (2) = 1 $$
With $n=2^x$, I have the following equation. Am I wrong in this ...
1
vote
1
answer
114
views
A fun double sum involving binomial coefficients
I came across the following double sum expression:
$$
S(k) := \sum_{l=0}^{2(k+1)-1} \sum_{i=0}^{l} (-1)^i\binom{2(k+1)-i}{2(k+1)-l}
\left[ 3\binom{2k}{i-2}+ 3k\left(\binom{2k}{i-1} -
\binom{2k-1}{i-2}\...
2
votes
4
answers
258
views
Coefficient of $x^k$ in polynomial
Let $k, n, m \in \mathbb{N}, k \le n.$ Find the formula for coefficient of $x^k$ in $(x^n + x^{(n-1)} + ... + x^2 + x + 1)^m$.
answer is in this question: faster-way-to-find-coefficient-of-xn-in-1-x-...
2
votes
2
answers
108
views
A general formula for $\mathcal{F}_{n} = \prod_{i=1}^n (a_ix + b_iy)$
So I am trying to simplify following product, $$\mathcal{F}_{n} = \prod_{i=1}^n \left(a_ix + b_iy\right)$$ in terms of products and summation. This is what I have come up with so far.
We see that for ...
2
votes
1
answer
95
views
General formula for $\sum_{k=0}^n k^a \binom{n}{k}$ is somehow hypergeometric? [duplicate]
Original question is a duplicate of this question. Please refer to after the edit
Original question:
I was investigating formulas of the form
$\sum_{k=0}^n k^a \binom{n}{k}$ after noticing on ...
3
votes
1
answer
75
views
How to prove that this binomial sum remains positive for $x>1$?
Let's say you have this function for real numbers $x>1$, for some positive integer $n \geq 1$
$$
\sum_{k=0}^{\left \lfloor n/2 \right \rfloor} {x \choose 2k+\frac{1-(-1)^n}{2}}
$$
How would you ...
0
votes
1
answer
87
views
Simplifying a sum of binomials, is there a closed form?
I am struggling with a formula that I derived, which (I believe) can be simplified further.
In principle, I want to determine the coefficients of the following polynomial:
\begin{align}
p(x) = (1+x+.....
2
votes
1
answer
123
views
Alternative expressions for Krawtchouk (Kravchuk) polynomials
For fixed non-negative integers $n$ and $q \geq 2$, the $k$-th Krawtchouk (Kravchuk) polynomial is defined as
$$K_k = \sum_{j=0}^k (-1)^j (q-1)^{k-j} \binom{X}{j} \binom{n-X}{k-j} \in \mathbb{Q}[X]$$
...
1
vote
0
answers
67
views
Closed formula for $\sum_{k=0}^{\lfloor n/2\rfloor} x^k\binom{n-k}{k}$
Let $$P_n(x) = \sum_{k=0}^{\lfloor n/2\rfloor} x^k\binom{n-k}{k}.$$ It's known that $P_n(1) = F_{n+1}$, the $(n+1)$th Fibonacci number, see for example here. Can we find a closed form for this ...
1
vote
1
answer
43
views
Prove that the 5-adic valuation of $(10^{k+t}+10^t+1)^c-1$ is $t+v_5(c)$
Here is a result of mine that I really wish to be strictly proven (I need it as an intermediate lemma for a theorem).
Let $v_5(a)$ indicate the $5$-adic valuation of $a \in \mathbb{Z}^+$.
How can we ...
1
vote
1
answer
89
views
Asymtotic of some binomial sum
Assume $n$ is a positive odd integer, I need to find the asymptotic as $n$ goes to infinity of the sum
$$s(n,x)=\frac1x\sum_{k=0}^n (-1)^k\binom{-x-\frac12}{k}\binom{x-\frac12}{n-k},$$
where the ...
3
votes
1
answer
162
views
Prove combination of polynomials must be odd polynomials with positive coefficients.
Let $m,n\geq0$ are integers, show that
$$p_{m,n}(x)=\sum_{k=0}^{m} \binom{2x+2k}{2k+1} \binom{n+m-k-x-\frac{1}{2}}{m-k}$$
must be an odd polynomial(all coefficients of even power of $x$ is $0$) with ...
2
votes
0
answers
56
views
$f_n(ab) = f_n(a)f_n(b) + f_n(a-1)f_n(b-1) + f_n(a-2)f_n(b-2)+ ...+f_n(a-n)f_n(b-n)$
I was toying around when I noticed for $a,b > 0$:
$$f(ab) = f(a)f(b) + f(a-1)f(b-1)$$
is satisfied by $f(n) = T_n$ ; the triangular numbers $n(n+1)/2$.
This equation is not an addition formula, not ...
2
votes
0
answers
70
views
Expectation of a certain polynomial expression in Rademacher random variables.
Let $N_1,k \ge 1$ be integers and let $N = N_1 k$. Let $G_1,...,G_k$ be an equi-partition of $[N] := \{1,2,\ldots,N\}$. Thus, $|G_j| = N_1$ for all $i$. Let $\mathcal S$ be the transversal of this ...
6
votes
1
answer
194
views
Conjecture: Shallow diagonals in Pascal's triangle form polynomials whose roots are all real, distinct, and in $(-2,2)$.
Here are the first few "shallow diagonals" in Pascal's triangle.
We can use these shallow diagonals to make polynomials. Note that the even degree polynomials have an extra $\pm x$ at the ...
5
votes
1
answer
215
views
Series of polynomials very nearly follows binomial coefficients but doesn't quite
I'm modelling a system using a Markov chain and by a few iterations of the transition matrix I can see a pattern emerging in the resulting polynomial that really looks like Pascal's triangle, but isn'...
1
vote
2
answers
153
views
Find the coefficients of product
Given the following product,
$$(1+ax)(1+a^2x)(1+a^3x)\cdots (1+a^mx) $$
where $a$ is some real number which will be taken to be unity in the end. I want to know the coefficient of general term of ...
5
votes
2
answers
169
views
Prove that $\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$
For arbitrary $x$ and $1\leqslant m\leqslant n$, prove the following:
$$\sum_{k=1}^n\frac{\prod_{1\leq r\leq n, r\neq m}(x+k-r)}{\prod_{1\leq r\leq n, r\neq k}(k-r)}=1$$
I'm looking for a proof that ...
1
vote
1
answer
97
views
Sum with binomial coefficient using identity
I want to prove:
$\displaystyle \sum_{k=0}^n (-1)^k \binom{x}{k} = (-1)^n \binom{x-1}{n}$
using: $(1-z)^x \cdot \frac{1}{1-z} = (1-z)^{x-1}$
I know how to do it with induction but i somehow can't ...
0
votes
0
answers
42
views
Expressing $j$-nomial coefficients in terms of binomial coefficients
Call the $k$th coefficient of $\left(\sum_{i=0}^jx^i\right)^n$ the $j$-nomial coefficient $C(n,k,j)$, so that the numbers $C(n,k,2)$ are just the binomial coefficients $\binom{n}{k}$. From the OEIS ...
0
votes
1
answer
51
views
Show with the help of binomial theorem that these two equations are equal?
Show with the help of binomial theorem that these two expression are equal for $n\ge 0$ then this $$ \sum_{k=0}^n \binom n k x^k (2+x)^k = \sum_{k=0}^{2n} \binom {2n} k x^k $$
I don’t know how to do ...
7
votes
3
answers
275
views
Proof of a neat pattern in polynomials
Let $f_1:\mathbb{R}\to\mathbb{R}$ such that $$f(x) = ax + b\space\space \forall\space x \in \mathbb{R}$$
It can be easily verified that $$f(x)-2f(x-1)+f(x-2)=0 \space \forall \space x \in
\mathbb{R}--...
3
votes
1
answer
889
views
What is the most efficient algorithm to evaluate a polynomial of n degree at K points?
A brute force approach would be to evaluate each point for each of the terms of a polynomial, which will be $O(Kn^2)$.
If we use logarithmic exponentiation to find each $x^i$ then it becomes $O(Kn \...
1
vote
0
answers
50
views
Nonnegative integer combinations of binomial coefficients
A classical result of Polya and Ostrowski states that integral linear combinations of binomial coefficients ${x\choose k}$ is exactly the set of all polynomials $f(x)\in\mathbb{Q}[x]$ such that $f(\...
2
votes
1
answer
129
views
Concrete Mathematics: What is polynomial argument
In the book Concrete Mathematics: A foundation for Computer Science of the chapter Binomial Coefficients, It gives an identity
$$
(r - k) {r \choose k} = r {r - 1 \choose k}
$$
for positive integers r....