Tag Info

New answers tagged

0

Upto an integer scalar multiple, $P_n(x)$ is the truncation of $e^x$. It was proved by Schur that this polynomial is irreducible (cannot be factorized as product of lower degree polynomials with rational coefficients). T N Shorey has worked in generalizing this result. It will have results relevant to your quest.


0

After Jack's comment, it seems that $$P_n(x)=e^x \,\Gamma (n+1,x)$$ match the expression so $$P_{n+1}(x)=\frac{\Gamma (n+2,x)}{\Gamma (n+1,x)}\,P_n(x)$$ Now, the name ?


0

Hint With a hard problem it's sometimes easier to consider an easier one. Suppose the problem was finding the number of ways to distribute £5 to $n$ people. For $n=1$ There is no choice but to give them all the money. $\circ \circ\circ\circ \circ $ For $n=2$ I can share out the money by inserting a blue bar in the gaps of the coins to show who gets ...


0

You know that $G_X(z)= (1-p+pz)^n$ and that $G_{Y\mid X}(z\mid j) = (1-q-qz)^{n+j}$ . Further, recall that $G_W(z) = \mathsf E(z^W)$. Thus to find the unconditional probability of $Y$ use the Law of Iterated Expectation. $$\begin{align}G_Y(z) & = \mathsf E(z^Y) \\ & = \mathsf E(\mathsf E(z^Y\mid X)) \\ & =\mathsf E(G_{Y\mid X}(z\mid ...


3

You want to kill the terms of odd degree, which can be done by projecting onto the space of even power series parallel to the space of odd power series (the two spaces are complementary inside the space of all power series). If your generating series is given by an expression $A(x)$ (and unless you are working over a field of characteristic$~2$, which I will ...


0

Hints: To quote Wikipedia: The normalization of the probability density function can be expressed in terms of the generating function by $$\operatorname{E}(1)=G(1^-)=\sum_{i=0}^\infty f(i)=1.$$ $P(X=0)=G(0)$


1

Let us set $A(X)$ the generating function whose coefficients are $(a_n)$. I claim that : $$A(X)-\frac{1}{1-X}=\sum_{n=1}^{\infty}(2^n-1)X^{2n}=\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2n} $$ $$\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2n}=X^2\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}2^kX^{2(n-1)}=X^2\sum_{n=0}^{\infty}\sum_{k=0}^{n}2^kX^{2n} $$ Now the last ...


2

The problem is your first generating function. What you have typed is the generating function for the sequence $(0,1,2,4,8,16,...)$. The correct generating function is $$\sum_{n = 0}^\infty2^nx^{2n} = \frac{1}{1 - 2x^2}$$. Once you have made this correction, your second step should work in producing the right generating function for the entire sequence.


1

Best do a series expansion around $x=0$. In your case, your favorite computer algebra system yields: $$ \frac{2 e^x}{e^{2x}+1+2x} = 1-x+3/2 \cdot x^2 -5/2 \cdot x^3+ 31/8 \cdot x^4+ O(x^5) $$ This is before multiplying each coefficient by $n!$. Since the series is alternating, I don't think it actually "counts" anything. Maybe the sum of this series and ...


4

We start with the key identity: $$\sum\limits_{j=1}^{n-k} \frac{(-1)^{j-1}}{j}\binom{n}{k+j} = \binom{n}{k}(H_n - H_k)$$ which can be proved elementarily by induction on $n$ or otherwise. Thus we have for our special case: $\displaystyle \binom{2n}{n}(H_{2n} - H_n) = \sum\limits_{j=1}^{n} (-1)^{j-1}\frac{1}{j}\binom{2n}{n+j}$ The series then decomposes ...


2

Answer summary: The generating function $r(u) = 1 + 3 u + 21 u^2 + 183 u^3 + 1773 u^4 \cdots$ is the unique solution to $$ 4 - 3 r(u)^2 - r(u)^3 + 27 r(u)^3 u=0 \qquad (\ast) $$ with $r(0)=1$. We can use this formula to generate many terms quickly, and to determine the asymptotic behavior of the sequence. To a first approximation, the sequence grows like ...


2

Expanding on Did's comment: $$ \begin{align} \frac{x^2}{(1-2x)(1-x)} &= x \, \frac{1}{1-2x} - x \, \frac{1}{1-x} \\ &= x \sum_{n=0}^{\infty} 2^n x^n - x \sum_{n=0}^{\infty} x^n \\ &= \sum_{k=1}^{\infty} (2^{k-1}-1) x^k \end{align} $$ Thus the first eight terms $a_0,\dotsc,a_7$ of the sequence $(a_k)_{k\geq0}$ are $$ 0, 0, 1, 3, 7, 15, 31, 63 $$


2

Using the geometric series, $$\frac1{1-x}=\sum_{n=0}^\infty x^n$$ and $$\frac1{1-2x}=\sum_{n=0}^\infty 2^nx^n.$$ Now, multiply this series and then multiply by $x^2$ and list the first 8 coefficients of the resulting series. To multiply two power series, $\sum a_nx^n$ and $\sum b_nx^n$. $$\begin{align} & ...


0

Hints If we find what $a_n$ is, the generating function should be easy to get from its definition. To find $a_n$, define $x_1. \ldots x_{100}$ the amount of dollars given person $i$. You need to make sure $\sum_{i=1}^{100} x_i = 100$. How many solutions does this system have?


3

There may be some cases where complex variables, the residue theorem and the residue at infinity are helpful. Suppose your OGF is $f(z)$ and the desired EGF is $g(w).$ Then we have $$g(w) = \sum_{n\ge 0} \frac{w^n}{n!} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} f(z) \; dz.$$ This will simplify together with some conditions on convergence ...


1

We can obtain coefficients of $\frac{1}{(1-x)^5}$ by: $p_k = {5+k-1 \choose k}$. We know that $(x-x^7)^4$ to get $x^{15}$ we only need ${4 \choose 0} \cdot x^{4}$ and ${4 \choose 1} \cdot (x)^{3}(-x)^{7}$. We will need the coefficients of $p_k$ for $x^{11}$ and $x^{5}$. So: ${4 \choose 0} \cdot {15 \choose 11} x^{15} - {4 \choose 1} \cdot {9 \choose 5} ...


1

Let $F,G$ be independent random variables distributed according to $f,g$, and let $H \sim F+G$. You are given that for all $k,\ell$, $$ \Pr[F=k|F+G=\ell] = \binom{\ell}{k} p^k (1-p)^{\ell-k}. $$ That gives us $$ \Pr[F=k] = \sum_{\ell=0}^\infty \binom{\ell}{k} p^k (1-p)^{\ell-k} \Pr[F+G=\ell] = \frac{p^k}{(1-p)^k} E[\binom{H}{k} (1-p)^H]. $$ Let $\rho = ...


0

$$ \dfrac{\left(x-x^7\right)^4}{\left(1-x\right)^5} = \dfrac{x^4\,\left(x+1\right)^4\,\left(x^2-x+1\right)^4\,\left(x^2+x+1\right)^4}{1-x} $$ I think this is the best you can do and I sadly do not really know what you mean by extract.


1

You ask "Did I go wrong somewhere...?" I'm having trouble following at a number of points in your post, which may be a sign that something is wrong, or at least of some things that ought to be clarified. You say The number of returning paths on 3-regular graphs of length $r$ without backtracking may be written as $2^{-r/2}p_r(x/\sqrt{2})$ which is a ...


1

Use the definition of a probability generating function and the Law of Iterated Expectation: $\begin{align} G_Y(z) & = \mathsf E(\mathsf E(z^Y\mid X)) \\ & = \mathsf E(G_{Y\mid X}(z)) \\ & = \mathsf E((qz+1-q)^{n+X}) \\ & = (qz+1-q)^n\mathsf E((qz+1-q)^{X}) \\ & = (qz+1-q)^n G_{X}(qz+1-q) \\ & = (qz+1-q)^n ...


2

$$G_{Z}\left(z\right)=\sum_{j=0}^{n}\mathbb{E}\left(z^{n+j-Y}\mid X=j\right)P\left(X=j\right)=\sum_{j=0}^{n}z^{n+j}G_{Y\mid X=j}\left(z^{-1}\right)P\left(X=j\right)=\sum_{j=0}^{n}z^{n+j}\left(qz^{-1}+\left(1-q\right)\right)^{n+j}P\left(X=j\right)=\left(q+\left(1-q\right)z\right)^{n}G_{X}\left(q+\left(1-q\right)z\right)$$


1

If you are familiar with homogenic recursions: You can write the characteristic equation: $x^{n+2} = x^{n+1}+2x^n \rightarrow x^2=x+2 \rightarrow x^2-x-2=0$. Your solutions are: $x_1=2, x_2=-1$. Therefore, your recursion have the followning form. $x_n = \alpha * 2^n + \beta *(-1)^n$ Now, to make it correct, we need to get $\alpha$ and $\beta$ with your ...


3

Define $A(x)=\sum_{n\ge 0} a_n x^n$ as the generating function for $(a_n)$. Then, the given recurrence gives you, $$A(x)-(a_1x+a_0)=x(A(x)-a_0)+2x^2A(x)\\\implies A(x)=\frac{-3x}{2x^2+x-1}=-\frac{3x}{(2x-1)(x+1)}=\left(\sum_{n\ge 0}(2x)^n-(-1)^nx^n\right)\\\implies a_n=(2^{n}+(-1)^{n+1}),\ n\ge 1$$


1

First Step Write the equation in standard form. $$a_{n+2} - a_{n+1} -2a_n = 0$$ Now write the characteristic equation. $$r^2 - r - 2 = 0$$ $\iff r_1 = 2 $ & $r_2 = -1$ Thus we know the general form of the homogeneous equation is: $$a_n = c_1{2}^n + c_2({-1})^n$$ Second Step Use the initial conditions. $$a_0 = 0$$ $$a_1 = 3$$ We get: ...


2

For every divisor $d$ of $n$, there are exactly two strings with length $n$ and block length $d$: one starts with $0$'s and the other starts with $1$'s. So if $f(n)$ is the number of binary strings composed of equal block lengths, then $f(n)=2d(n)$ where $d(n)$ counts the number of divisors of $n$. The ordinary generating function of $f$ is $2\sum_n ...


1

Recall that $$\frac1{1-x}=\sum_{n=0}^\infty x^n.$$ So $$\frac{\mathsf d^7}{\mathsf dx^7}\left[\frac1{1-x}\right] = \frac{7!}{(1-x)^8}$$ and $$\begin{align*} \frac{\mathsf d^7}{\mathsf dx^7}\sum_{n=0}^\infty x^n =\sum_{n=7}^\infty \frac{n!}{(n-7)!}x^{n-7}=\sum_{n=0}^\infty\frac{(n+7)!}{n!}x^{n} \end{align*}$$ Hence $$\begin{align*}\frac{1+3x}{(1-x)^8} ...


0

In series form: $\sum\limits_{n=0}^{\infty}\dfrac{J_n(n)}{n!}=\sum\limits_{n=0}^{\infty}\sum\limits_{k=0}^\infty\dfrac{(-1)^kn^{n+2k}}{n!k!(n+k)!2^{n+2k}}$


2

Well, the usual generating function for the number $p(n)$ of partitions of an integer $n$ is given by : $$\prod_{n=1}^{\infty}(1+x^n+x^{2n}+x^{3n}+...)=\prod_{n=1}^{\infty}\frac{1}{1-x^n} $$ Following the same argument (there is something missing in the formula you have given), the generating function for the number of partitions of an integer where each ...


1

The last step simply follows from calculating the coefficient of $x^{n}$ in the power series expansion of $\dfrac{1}{(1-x)^k}$: \begin{align} \dfrac{1}{n!} \cdot \text{$n$-th derivative of } \dfrac{1}{(1-x)^k} &= \dfrac{1}{n!} \cdot (-1)^{n} (-k) (-k-1) \dots (-k -n+ 1) \\&= \dfrac{(n + k - 1) \dots (k+1) k}{n!} \\=& \dfrac{(n+k-1)!}{n! ...


1

The answer is not immediately obvious but you can do it combinatorially as follows. Firtly, $f(n,k)$ counts the number of solutions to the equation $n_1+\cdots+n_k = n$ in non-negative integers. To see the value of $f(n,k)$ consider the classic argument of separating $n$ balls into $k$ bins with $k-1$ separators. For example with $n = 5$ and $k = 4$, one ...


3

You correctly expanded the RHS as $$(e^x)^3-3x(e^x)^2+3e^xx^2-x^3$$ Now write this as $$(e^{3x})-3x(e^{2x})+3e^xx^2-x^3$$ We look to the Taylor series of $e^{3x}$, found by substituting $y=3x$ in the Taylor series of $e^x$: $$e^{3x} = 1+3x+\frac{3^2x^2}{2!} + \frac{3^3x^3}{3!} + \cdots + \frac{3^{10}x^{10}}{10!} + \cdots $$ Can you find those form ...


1

The generating function for partitions by parts each of which appears at most $k$ times is $$\prod_{q\ge 1} \sum_{m=0}^k x^{qm} = \prod_{q\ge 1} \frac{1-x^{q(k+1)}}{1-x^q}.$$ This is $$\prod_{q\ge 1} \frac{1}{1-x^q} \prod_{q\ge 1} \left(1-x^{q(k+1)}\right).$$ The first term here generates ordinary partitions and the second one cancels the parts that are a ...


1

Hint: you already did a very similar sum in showing that your distribution actually is a probability distribution.


0

HINT: $$a_n=\frac{x^{n+1}-1}{x-1}$$ if $x\ne 1$ and inserting this term in the next equation we obtain $$b(n)=x^{n-1} \left(c_1+\frac{x^2 \left(-x^{-n}+x^{n+3}-(2 n+3) x^2+(2 n+3) x\right)}{(x-1)^2}\right)$$


2

The only approach I can think of is to note that the functional equation is multiplicative, so this suggests taking the logarithm and defining $g(x) = \log f(x)$ to obtain the additive equation $$g(1-p+ps) + g(p) = g(ps).$$ Now consider when $s = 1$, we get $g(1) + g(p) = g(p)$, so $g(1) = 0$, hence $f(1) = 1$. Next, setting $s = 1/p$ gives $g(2-p) + g(p) ...


1

Note: OP is asking for a more combinatorially answer. This one is based upon binomial inverse pairs. According to OPs question the exponentially generating function (egf) \begin{align*} F(x)=\sum_{n\geq 0}f_n\frac{x^n}{n!}=e^{x+\frac{x^2}{2}} \end{align*} has coefficients of the form \begin{align*} f_n=\sum_{k\geq ...


2

As mentioned in Karl's answer, one surefire way of doing it is by adding together all coefficients of $(x+x^2+x^3+x^4+x^5+x^6)$ on the terms of power less than or equal to $14$. You have included in your proposed solution a very nice way to get around the difficulty of having to either personally sum or word to the computer how to sum all of those ...


1

The probability generating function for rolling a normal die is: $G(t)=\frac{t}{6} + \frac{t^2}{6} + \frac{t^3}{6} + \frac{t^4}{6} + \frac{t^5}{6} + \frac{t^6}{6}$ To find the probability generating function for the sum of four independent dice then you have $G_S(t)=\left(\frac{t}{6} + \frac{t^2}{6} + \frac{t^3}{6} + \frac{t^4}{6} + \frac{t^5}{6} + ...


1

Following Alexey Burdin's comment, this is basically an application of the generalized binomial theorem for: $$\frac{1}{(1-x)^s}=\sum_{k\geq 0} \binom{s+k-1}{s-1}$$ So the answer follows by using the general binomial expansion for $1/(1-x)^s$ for $s=5$. The polynomial terms are there to correct the first set of entries because the first few terms will be ...


1

If you are allowed to use standard/well-known generating functions such as: $n^2=\frac{x (x+1)}{(1-x)^3};~n=\frac{x}{(1-x)^2};~1=\frac{1}{1-x}$, then you can simply calculate $f(x)$ as $$f(x)=3\left[\frac{x (x+1)}{(1-x)^3}\right]+4\left[\frac{x}{(1-x)^2}\right]+5\left[\frac{1}{1-x}\right]=\frac{(3-4 x) x-5}{(x-1)^3}.$$


0

Let $$f(z) = \sum_{n=0}^\infty a_nz^n = \sum_{n=0}^\infty (3n^2 + 4n + 5)z^n.$$ Note that we can write $$ 3n^2 + 4n + 5 = 3n(n+1) + n + 5.$$ Hence $$\begin{align*} f(z) &= \sum_{n=0}^\infty(3n(n+1) + n + 5)z^n\\ &= 3\sum_{n=0}^\infty n(n+1)z^n + \sum_{n=0}^\infty nz^n + 5\sum_{n=0}^\infty z^n\\ &= 3z\sum_{n=0}^\infty (n+1)(n+2)z^n + ...


1

The first is the generating function $$ \sum_{n=0}^\infty(3\,n^2+4\,n+5)t^n = 3\sum_{n=0}^\infty n^2\,t^n+4\sum_{n=0}^\infty n\,t^n+5\sum_{n=0}^\infty t^n\tag{1} $$ But a bit of calculus and the identity $$ \sum_{n=0}^\infty t^n=\frac{1}{1-t}\tag{2} $$ gives us \begin{align*} \sum_{n=0}^\infty n^2\,t^n&=\frac{t(t+1)}{(1-t)^3} & \sum_{n=0}^\infty ...


2

The trick is usually to use the formula $$ \sum_{n=0}^\infty \binom{n+k}{k} x^n = \frac{1}{(1-x)^{k+1}}. $$ You can express $3n^2+4n+5$ as a linear combination of $\binom{n+2}{2},\binom{n+1}{1},\binom{n+0}{0}$, thereby solving part (a). You can solve part (b) in a similar way, but there is a shortcut. We know what $\sum_{n=0}^\infty \binom{n+4}{4} x^n$ ...


3

Since $\displaystyle \frac{1}{(1-x)^n}=(1-x)^{-n}=\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^k$, $\displaystyle \frac{x^n}{(1-x)^n}=\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^{n+k}=\sum_{m=n}^{\infty}\binom{m-1}{m-n}x^m=\sum_{m=n}^{\infty}\binom{m-1}{n-1}x^m$ $\;\;$(letting $m=n+k$)


3

It’s the binomial theorem, $$(a+b)^n=\sum_{k\le n}\binom{n}ka^kb^{n-k}\;.$$ Now let $a=1+x$ and $b=-1$. In this case taking the sum over $k\le n$ is equivalent to taking it from $k=0$ to $k=n$: by definition $\binom{n}k=0$ if $k<0$.


0

As I mentioned in my original post, I was not comfortable with the reasoning. We can think of negative-multinomial as a multinomial of size M $(M:0\rightarrow \infty)$ mixed with $k-1$ occurences of type $0$ event, which can happen in $\binom{M+k-1}{k-1}$ ways, followed by the last occurrence of the type $0$ event; which terminates the trials. Thus the ...


2

I've checked some parts of your question. Your approach seems feasible and many calculations look quite ok. But I see two possible sources of problems: When calculating the derivative of e.g. $$ \lambda_{n,c}(x) = \sum_{k=c}^n \sum_{j=0}^{k-c} {k-c \choose j} \ln(g(x))^{k-c-j} \frac{d^j}{df^j}[f(x)_c] B_{n,k}^{(f \diamond g)^c}(x) $$ and we take ...


3

Let $f(z) = \sum\limits_{n=0}^\infty a_n z^n$. Multiply the defining recurrence relation $$a_n = a_{n-1} + 2 a_{n-2} + 3,\quad n \ge 2$$ by $z^n$ and start summing from $n = 2$, you get $$ \underbrace{f(z) - \overbrace{(2 + 2 z)}^{a_0 + a_1 z}}_{ \sum\limits_{n=2}^\infty a_n z^n = f(z) - a_0 - a_1 z} = \underbrace{z(f(z)-\overbrace{2}^{a_0})}_{ ...


2

My preferred method is that of Graham, Knuth, & Patashnik, Concrete Mathematics. First rewrite the recurrence so that it’s valid for all $n$ if one assumes that $a_n=0$ for all $n<0$. In this case we get $$a_n=a_{n-1}+2a_{n-2}+3-[n=0]-3[n=1]\;,$$ where the last two terms contain Iverson brackets and are there to get the initial conditions right. Now ...


2

$a_{n+2}+\frac32=a_{n+1}+\frac32+2(a_n+\frac32)$. Now put: $b_n=a_n+\frac32\,$, then: $b_{n+2}=b_{n+1}+2b_n$



Top 50 recent answers are included