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 ...
- 565
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 ...
- 39
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 ...
- 389
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 $...
- 10.1k
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 ...
- 135
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}\...
- 336
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-...
- 311
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 ...
- 141
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 ...
- 245
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 ...
- 633
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+.....
- 31
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]$$
...
- 23.1k
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 ...
- 10.5k
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,160
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 ...
- 134
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 ...
- 134
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 ...
- 16.4k
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 ...
- 9,575
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 ...
- 25.7k
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'...
- 53
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 ...
- 505
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 ...
- 848
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 ...
- 121
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 ...
- 2,346
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 ...
- 51
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}--...
- 271
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 \...
- 491
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(\...
- 427
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....
- 465
2
votes
3
answers
184
views
Combinatorial interpretation of polynomials
I'm reading a proof for the following identity:
$$\sum_{k}A_{k}(r,t)A_{n-k}(s,t) = A_{n}(r+s, t), \qquad \text{integer} \ n \geq 0 \tag{1}$$
where $A_{n}(x,t)$ is the $n$th degree polynomial in $x$ ...
- 673
1
vote
1
answer
90
views
Residue of division of $x^n$ by $1-x$?
Is there a name for the residue of dividing $x^n$ by $(x-1)^m$, where $n>m$?
Obviously, it is a polynomial $P$ of degree $m-1$. It is easy to see that the result of the division is $$x^{n-m} + \...
- 1,304
1
vote
1
answer
33
views
Simplify $\sum_{t=k}^{n} (\binom{n}{t} \cdot a^{t-1} \cdot (1 - a)^{n - t - 1} \cdot (t - n \cdot a))$
I was working on my probability theory homework and I found probability density function that looks as following
$$\sum_{t=k}^{n} \binom{n}{t} \cdot a^{t-1} \cdot (1 - a)^{n - t - 1} \cdot (t - n \...
- 983
1
vote
2
answers
96
views
Binomials to polynomial
What would be a nice way to conver the expression$$\binom{n}{2}+42\binom{n}{3} + 375\binom{n}{4} + 1450\binom{n}{5} + 2940\binom{n}{6} + 3360\binom{n}{7} + 1680\binom{n}{8}$$
to its corresponding $8-$...
3
votes
1
answer
135
views
Reciprocal binomial coefficient polynomial evaluation
The conventional binomial coefficient can be obtained via
$$
f(x, n) = (1+x)^n = \sum_{i=0}^n { n \choose i} x^i
$$
And the function $f$ can be every efficiently performed on evaluation.
I'm ...
- 1,271
2
votes
1
answer
180
views
$p(q(t)) \neq q(p(t))$ for every $t$, find all degrees of monic polynomials
Find all the positive numbers $m, n$ for which there exist some monic polynomials $p$ and $q$, for which $\deg p = m$ and $\deg q = n$, while $f \circ g$ and $g \circ f$ have no intersection points.
...
3
votes
1
answer
330
views
Expressing polynomials as a linear combination of $\binom{x}{k}$
If we have an arbitrary polynomial, $P:\mathbb{N}\to\mathbb{R}$, how can we express $P(x)$ as a linear combination of $\binom{x}{k}$. Is there any easy formula for finding this expression.
I am pretty ...
- 5,182
6
votes
2
answers
121
views
Is the sum $\sum_{k=0}^n{n \choose k}\frac{(-1)^{n-k}}{n+k+1}$ always the reciprocal of an integer $\big(\frac{(2n+1)!}{(n!)^2}\big)$?
Denote the sum $$S_n := \sum_{k=0}^n{n \choose k}\frac{(-1)^{n-k}}{n+k+1}$$
This value arose in some calculations of polynomial coefficients. I'm not used to dealing with expressions of this sort. ...
- 1,044
1
vote
0
answers
120
views
Proving this equation involving derivative of a rook polynomial.
So, there is an exercise in Section 8.3 in Alan Tucker's Applied Combinatorics regarding rook polynomials. The problem is as follow.
Let $R_{n, m}(x)$ be the rook polynomial for an $n \times m$ ...
- 11
6
votes
4
answers
182
views
True or false: If you square the coefficients in the expansion of $(x+1)^n$, the resulting polynomial has $n$ distinct real roots.
It seems that if you square the coefficients in the expansion of $(x+1)^n$, the resulting polynomial has $n$ distinct real roots. (I experimented using desmos.com.)
In other words, I am looking for a ...
- 25.7k
0
votes
2
answers
193
views
AIME 1986 Problem - Polynomials
OBSERVATIONS
Let $$f(x)=1-x+x^2...+x^{16}-x^{17}$$
If we try to replace $x=y-1$ then we see that $y^2$ appears in every term after $1-x$ in $f(x)$.
By Binomial Expansion/observation Coefficient of $y^...
- 129
-1
votes
1
answer
77
views
What is the coefficient of $x^{11}$ in $(x+x^2+x^3+x^4+x^5)^4(1+x+x^2+...)^4$?
I got
$$(x+x^2+x^3+x^4+x^5)^4=x^4((1-x^5)/1-x)^4$$
and
$$(1+x+x^2+...)^4=1/(1-x)^4,$$
what I should do next? Please help me with it, thank you.
- 1
1
vote
1
answer
72
views
If $p$ is a prime and $m,n\in\mathbb{N}$, prove that $\binom{pm}{pn}\equiv\binom{m}{n}$ mod $p$.
Hint: Compare the binomial expansions of $(1+x)^{pm}$ and of $(1+x^m)^p$ in $\mathbb{F}_p[x]$.
If $R$ is a commutative ring, then the set of all polynomials with coefficients in $R$ is denoted by $R[x]...
- 366
-1
votes
3
answers
55
views
I need to develop $P_n(X)=\frac{(X+i)^{2n+1} - (X - i)^{2n+1}}{2i}$ using the binomial coefficients formula and show a few properties [duplicate]
In the previous questions I've proved that $(1+i)^{2n+1}=a_n+ib_n$ where $a_n$ and $b_n$ are $\pm 2^n$ and that $(1-i)^{2n+1}=a_n - ib_n$ and that $|P_n(1)|=2^n$ using the previous statements. But now ...
- 143
1
vote
1
answer
225
views
Reverse order of polynomial coefficients of type $\left(r-x\right)^n$
I have a simple question.
I have a polynomial defined by
$$
\left(r-x\right)^n = a_0 + a_1 x + ... + a_n x^n
$$
Is there a simple expression if I put the coefficients in reverse order?
$$
a_n + a_{n-1}...
- 399
1
vote
1
answer
42
views
Show that $P_n(X)=\frac{(X+i)^{2n+1} - (X - i)^{2n+1}}{2i}$ is of degree $2n$, even..., using the binomial coefficients formula [duplicate]
In the previous questions i've proved that $(1+i)^{2n+1}=a_n+ib_n$ where $a_n$ and $b_n$ are $\pm 2^n$ and that $(1-i)^{2n+1}=a_n - ib_n$ and that $|P_n(1)|=2^n$ using the previous statements. But now ...
- 143
1
vote
1
answer
174
views
What is the constant term in the expansion of ${\left(x^2-\dfrac{1}{x^4}\right)}^{13}$ ? and the middle term in it?
I want to determine the constant term and middle term in the expansion of ${\left(x^2-\dfrac{1}{x^4}\right)}^{13}$, I know that the constant term in the expansion of $(x+a)^n$ is always $a^n $, We can ...
6
votes
4
answers
258
views
If $P(x)$ is any polynomial of degree less than $n$, show that $\sum_{j=0}^n (-1)^j\binom{n}{j}P(j)=0$. [duplicate]
If $P(x)$ is any polynomial of degree less than $n$, then prove that
$$\sum_{j=0}^n (-1)^j\binom{n}{j}P(j)=0$$
My approach was to try and prove this separately for $j^k\ \ \forall\ \ k<n$, instead ...
- 641
3
votes
1
answer
56
views
Find all the values of a so that $3^{ \lfloor \frac{n-1}{2} \rfloor }\mid P_n{(a^3)}$ given the definition of $P_n$
Consider the polynomial $P_n{(x)} = \binom{n}{2}+\binom{n}{5}x + \cdots \binom{n}{3k+2}x^{k}$, where $n \ge 2$, $k= \lfloor \frac{n-2}{3} \rfloor$,
$(1)$ Show that $P_{n+3}{(x)}=3P_{n+2}{(x)}-3P_{n+1}{...
- 1,288
1
vote
0
answers
71
views
Why do two ways of expanding the same formal polynomial lead to matching coefficients?
There are a few proofs in which the technique is to expand the product of some formal polynomials in $\mathbb{R}[x_1,x_2,\ldots,x_k]$ in more than one distinct way and then we can match up the ...
- 3,415