New answers tagged

1

Perhaps somewhat easier: $$1-x+x^2-x^3=(1-x)(1+x^2)\implies\frac1{1-x+x^2-x^3}=\frac1{(1-x)(1+x^2)}$$ Now simple fractions: $$\frac1{(1-x)(1+x^2)}=\frac A{1-x}+\frac{Bx+C}{1+x^2}\implies1=A(1+x^2)+(Bx+C)(1-x)$$ Comparing coefficients for different values of $\;x\;$ , say for $\;x=1\;$ and coefficients of different powers of $\;x\;$ , we get: $$\begin{...


2

HINT Note that $$ f(x) = \frac{1}{1-x+x^2-x^3} = \frac{1+x}{1-x^4} = \frac{1}{1-x^4} + x \frac{1}{1-x^4} $$ You can write $$ \frac{1}{1-z} = 1 + z + z^2 + \ldots $$ So can you expand $f(x)$ into series and find the coefficient of $x^n$?


2

Quoting that very same Wikipedia article: Convergence and Mertens' theorem Let $(a_n)_n$ and $(b_n)_n$ be real or complex sequences. It was proved by Franz Mertens that, if the series $\sum_{n=0}^\infty a_n$ converges to $A$ and $\sum_{n=0}^\infty b_n$ converges to $B$, and at least one of them converges absolutely, then their Cauchy product ...


0

This answer may not follow the same line of reasoning but you might want to try out using derivatives and integrals of the generating function of $x^n$. For example, the derivative of $1+x+x^2...+x^s$ is $1+2x+3x^2...sx^{s-1}$. On the rhs, we can differentiate the generating functions of the corresponding series. The derivative of $\frac{1-x^{s+1}}{1-x} = \...


0

It's convenient to use the differential operator $D_x:=\frac{d}{dx}$ and the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series $A(x)=\sum_{k=0}^\infty a_kx^k$. Hint: Study the operator \begin{align*} [x^n]\frac{1}{1-x}(xD_x)^p \end{align*} applied on $\frac{1}{1-x}$. A detailed answer can be ...


2

Hint. An approach similar to what you are looking for. One may recall the general formula $$ \sum_{n=0}^\infty f(n)x^n=\frac1{1-x}\sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}\:\omega_n\left(\frac{x}{1-x} \right), \quad |x|<1, \tag1 $$ with the polynomials $$ \omega_n\left(x \right)=\sum_{k=0}^n \begin{Bmatrix}n\\k\end{Bmatrix}k!x^k \tag2 $$ where $\...


1

Here's one way of describing the answer. First, the Stirling numbers of the second kind $S(m, k)$ have the property that $$n^m = \sum_k S(m, k) (n)_k$$ where $(n)_k = n(n-1) \dots (n-(k-1))$. Second, the generating function of $(n)_k$ turns out to be relatively straightforward to write down: it is $$\sum_n (n)_k x^n = k! \frac{x^k}{(1 - x)^{k+1}}.$$ You ...


1

For simplicity, I will write $q_k$ for $P(S=k)$ and $p_k$ for $P(X=k)$ while dropping the subscripts on $S_0$ and $X_1$. Your double summation is not quite correct; when you exchange the order of summation the lower bound should be $i=(k-1)_+$, not $i=k-1$. This is because $i$ can never be negative. Of course, this only makes a difference when $k=0$. The ...


2

Yes: a power series $\sum_{k=0}^\infty a_kx^k$ is a probability-generating function if and only if $\sum_{k=0}^\infty a_k=1$ and $\forall k, a_k\ge0$. If $p(n)$ is the probability-mass function associated to $G$, then $\frac{p(n)\alpha^n}{G(\alpha)}$ is the one associated to $\frac{G(\alpha x)}{G(\alpha)}$. Notice that, since the radius of convergence of $G$...


1

Maybe the following may help you. If you have a linear recurrence of the form $$ u_{n+2}+a\cdot u_{n+1}+b\cdot u_n=0 \tag1 $$ then, multiplying out $(1)$ by $x^{n+2}$ and summing one gets $$ \sum_{n=0}^\infty u_{n+2}x^{n+2}+a\cdot \sum_{n=0}^\infty u_{n+1}x^{n+2}+b\cdot \sum_{n=0}^\infty u_nx^{n+2}=0\tag2 $$ or, with changes of index, $$ \sum_{n=2}^\infty ...


1

You can split this 2nd order recurrence relation into two 1st order recurrence relations. Define $b_0=0$ and $b_n=b_{n-1}+a$ for $n\geq 1$. In the same way define $c_0=1$ and $c_{n}=c_{n-1}+a$ for $n\geq 1$. Now we get $F_{2n}=b_n$ and $F_{2n+1}=c_n$, the first couple of terms of the generating function look like $$ F_0 + F_{1} x + F_{2} x^2 + F_{3} x^3 + \...


1

It’s easy enough to derive a closed form directly from the recurrences: $$\begin{align*} F_{2n}&=an\\ F_{2n+1}&=an+1 \end{align*}$$ Thus, $$\begin{align*} \sum_{n\ge 0}F_{2n+1}x^{2n+1}&=\sum_{n\ge 0}(an+1)x^{2n+1}\\ &=x\sum_{n\ge 0}anx^{2n}+\sum_{n\ge 0}x^{2n+1}\\ &=x\sum_{n\ge 0}F_{2n}x^{2n}+\frac{x}{1-x^2}\;, \end{align*}$$ so $$\...


2

You're correct the only way to make $x^{15}$ out of $-x^2$ and $-2x^9$ is to use three of the former and one of the latter. Therefore, using the binomial series, the coefficient should be $$\binom{-10}{3}(-x^2)^3\,\cdot\,\binom{-1}{1}(-2x^9)^1. $$ Now, $$\binom{-10}{3}=\frac{-10(-10-1)(-10-2)}{3\cdot2\cdot1}=-220, \qquad \binom{-1}{1}=-1 $$ (since $\...


5

Proposition : $$ f(z,a) = \int_{0}^{\infty} \dfrac{x^z}{x^2 +2ax +1} \mathrm{d}x = \dfrac{\pi}{\sin \pi z} \dfrac{\sin((1-z) \cos^{-1}(a))}{\sin(\cos^{-1}(a))}$$ Proof : Note that, $$ \sum_{n=0}^{\infty}{{U}_{n}(a) {(-x)}^{n}} = \dfrac{1}{x^2 +2ax+1} $$ where $ U_{n} (x) $ is the Chebyshev Polynomial of the second kind. $$ \implies \sum_{n=0}^{...


2

There are many proofs, most of them are elementary. For example: non-intersecting lattice paths and LGV-lemma — see e.g. Bressoud. Proofs and Confirmations (ch. 3) RSK-correspondence — see e.g. Stanley. Enumerative combinatorics (vol. 2, 7.20) counting lozenge tilings using condensation


2

For the first question, since $p+q=1$ it follows that $$ (p-q)^2=p^2-2pq+q^2=p(1-q)-2pq+q(1-p)=p+q-4pq=1-4pq $$ Therefore taking a square root yields $\sqrt{1-4pq}=|p-q|$. For the second question, while generating functions can be regarded as formal power series, they can also be viewed as defining an analytic function in some neighborhood of zero. There is ...


2

Note that $p_{n,m,s}$ can be broken into $$ p_{n,m,s} = p_{n,m,s}^{1} + p_{n,m,s}^{\geq 2}, $$ where $p_{n,m,s}^1$ is the number of ways to distribute $n$ balls into $m$ bins such that each bin has at most 1 ball and $p_{n,m,s}^{\geq 2}$ is the number of ways to distribute these balls so that at least 1 bin has at least 2 balls. Trivially, $p_{n,m,s} \geq p_{...


0

Using generating functions on the first one gets a bit messy; since it’s first order, you can simply ‘unwind’ the recurrence. In what follows I use the notation $$x^{\underline k}=\underbrace{x(x-1)\ldots(x-k+1)}_{k\text{ factors}}$$ for the falling factorial power. Shifting the index by $1$, we see that the recurrence can be written $i_n=2ni_{n-1}+2$. ...


0

After looking up generating functions, it seems like the answer would go as follows: The derivative of $F(x)=1-(1-x)^{1/2}$ is $\large F'(x)=1/2(1-x)^{-1/2}= \frac{1}{2\sqrt{1-x}}$. Since $\large U(x) = \frac{1}{\sqrt{1-x}}$, it follows that $F'(x) =\frac{U(x)}{2}$. If we want the coefficients for $F(x)$ we can integrate: $$F(x) = 1/2\Big(\frac{u_o x^1}{1}+...


0

By the Binomial theorem, $$(1+z^2)^r=\sum_{k=0}^r\binom rkz^{2k}$$ hence $G_{1,2k}=\binom rk$ and $G_{1,2k+1}=0$.


4

The beginning looks good, but I do not see how you justify the last line. I would use the geometric series instead: $$\begin{align*}\frac{x-3}{x^2-3x+2} &= \frac{2}{x-1} - \frac{1}{x-2}\\ &= -2\frac{1}{1-x} + \frac{1}{2}\frac{1}{1-\frac 12 x} \\ & = -2 \sum_{n=0}^\infty x^n + \frac{1}{2}\sum_{n=0}^\infty \frac{x^n}{2^n} \end{align*}$$ From that ...


0

Suppose $G(z)=g_{0}+g_{1}z+g_{2}z^{2}+\ldots$ If you take the $n$th derivative of $G(z)$ and evaluate it at $z=0$, you get $n!$ times the coefficient $g_{n}$. Thus evaluating derivatives of $G(z)$ at $z=0$ is a way to get at the coefficients $g_{n}$. For example, $G'''(z)=6g_{3}+24g_{4}z+60g_{5}z^{2}+\ldots$ and $G'''(0)=6g_{3}$. The formula given ...


0

There are $10^{15}$ squares. There are $10^{10}$ cubes. There are $10^6$ quints. There are $10^5$ powers to the 6 which are both squares and cubes. There are $10^3$ powers to the 10 which are both squares and quints. There are $10^2$ powers to the 15 which are both cubes and quints. And there are $10$ powers to the 30 which are all three. Apply ...


3

Since $10^{30}=(10^{15})^2=(10^{10})^3=(10^{6})^5=(10^5)^6=(10^3)^{10}=(10^2)^{15}$. Thus, the number of square is $10^{15}$, the number of cubes is $10^{10}$, the number of 5-th power is $10^6$, the number of 6-th power is $10^5$, the number of 10-th power is $10^3$, the number of 15-th power is $10^2$, and the number of 30-th power is $10$. Thus, there ...



Top 50 recent answers are included