Tag Info

New answers tagged

-1

I guess you want to compute the generating function for $s_i$ not $a_i$. $$A(x)=a_0+a_1x+a_2x^2+\ldots +a_ix^i+\ldots$$ And you want $$B(x)=s_0+s_1x+\ldots +s_ix^i+\ldots=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+\ldots +(\sum_{j=0}^ia_j)x^i$$ Doing some algebra, you will notice that ...


3

You want the notion of the convolution of two sequences. The convolution of the sequences $\alpha=\langle a_n:n\in\Bbb N\rangle$ and $\beta=\langle b_n:n\in\Bbb N\rangle$ is the sequence $\gamma=\langle c_n:n\in\Bbb N\rangle$ such that $$c_n=\sum_{k=0}^na_kb_{n-k}\;.$$ If $A(x)$ is the generating function for $\alpha$, and $B(x)$ is the generating function ...


2

I think that your idea to decompose in simple fractions is good. You can put $K=\mathbb{Q}(x)$, replace $\exp(x)$ by $y$, and decompose the following fraction in $K(y)$: $$\left(\frac{x}{y-1}\right) \left(\frac{x^2/2! }{y-1-x}\right) \left(\frac{x^3/3!}{y-1-x-x^2/2}\right)=\frac{A}{y-1}+\frac{B}{y-1-x}+\frac{C}{y-1-x-x^2/2}$$ To get $A$, you multiply by ...


2

Hint:$$\frac{x^7}{1-x} + \frac{2x^7}{1-x^2} \\=x^7\left( \frac1{1-x}+\frac2{1-x^2}\right) \\=x^7\left(\sum_{k=0}^\infty x^k+2\sum_{k=0}^\infty x^{2k}\right)$$


4

To say that $g(x)$ is the (ordinary) generating function of a sequence $\langle a_n:n\in\Bbb N\rangle$ is to say that $$g(x)=\sum_{n\ge 0}a_nx^n\;.$$ Let’s look at an example using some of the ideas that you need for your problem. Suppose that we want the generating function of the sequence $$\langle ...


1

Hint. Try to use that $$ \frac{1}{1-x^n} = 1 + x^n + x^{2n} + \dots $$


3

This is a subtle point. The idea is that when you were manipulating the power series for $f(x)$ you never said anything about whether or not the series converged -- in other words, you were formally manipulating the series. A formal power series is just a power series used without talking about convergence. To answer your question, $f(x)$ is not a function. ...


2

From $\alpha^2=A\alpha+B$, we immediately get that $\alpha^n=A\alpha^{n-1}+B\alpha^{n-2}$ for all $n\ge 2$. Likewise, $\beta^n=A\beta^{n-1}+B\beta^{n-2}$. Since both equations are linear, it does not hurt if we multiply them by constant factors $c,d$ and then add, i.e., we have $$(c\alpha^n+d\beta^n)=A( c\alpha^{n-1}+d\beta^{n-1})+B( ...


0

First, we want to manipulate things so that the subscript of the coefficients matches the exponents: \begin{align*} \textsf{LHS} &= \sum_{n=2}^{\infty}a_nx^n - 4\sum_{n=2}^{\infty}a_{n-1}x^n + 4 \sum_{n=2}^{\infty}a_{n-2}x^n \\ &= \sum_{n=2}^{\infty}a_nx^n - 4x\sum_{n=2}^{\infty}a_{n-1}x^{n-1} + 4x^2 \sum_{n=2}^{\infty}a_{n-2}x^{n-2} \\ ...


2

Since ultimately you would like the denominators of the partial fractions to have the form $1-ax$, I’d start by multiplying top and bottom by $-1$ to get $$\frac8{1-2x-3x^2}\;.$$ Now use your roots to factor the denominator, then set up the partial fraction decomposition: $$\frac8{1-2x-3x^2}=\frac8{(1-3x)(1+x)}=\frac{A}{1-3x}+\frac{B}{1+x}\;.$$ Now just ...


0

solve the equation $$a_{n+2}=5a_{n+1}-9a_n$$ with the ansatz $$a_n=q^n$$ and look for a special solution of the equation $$a_{n+2}=5a_{n+1}-9a_n+3n$$


3

There're at least two four commonly used methods: generating functions looking for solutions in a particular form: $n^k\alpha^n$ with $k\in\mathbb N$ and $\alpha\in\Bbb R$. Z-transform. Thank you, @Omnomnomnom. The annihiliator method/characteristic equations (even though they are closely related to the second method). Thank you, @anorton. The wikipedia ...


3

Your decomposition is incorrect. $$\begin{align} \frac{rBx}{(1-rx)(1-x)^2} & = \dfrac {U}{1-rx} + \dfrac V{x-1} + \dfrac W{(x-1)^2}\\ \\ &= \frac{U(x^2-2x+1)+ V(1 - rx)(x-1) + W(1-rx)}{(1-rx)(1-x)^2}\end{align}$$ Now try and solve for $U, V, W$.


0

My approach has been extremely empirical; so, please, forgive me for the lack of rigor ! What I first did was to develop as Taylor series (at $x=0$) to get $$\frac{(1+x)^5}{(1-x)^6}=1+11 x+61 x^2+231 x^3+681 x^4+1683 x^5+3653 x^6+7183 x^7+13073 x^8+22363 x^9+36365 x^{10}+O\left(x^{11}\right)$$ in which the coefficients are those given in both's answer. ...


1

In other words, you want to find the coefficient of $x^n$ in the Maclaurin series for the function $$f(x)=\frac{(1+x)^5}{(1-x)^6}=(1+x)^5(1-x)^{-6}.$$ To do that, first expand each factor using the binomial formula $$(1+u)^m=\sum_{n=1}^\infty\binom mnu^n$$ and then multiply the two binomial series together using $$\left(\sum_{n=0}^\infty ...


1

Yes, yours $n$-th numbers are called the Hilbert polynomials or quasi-polynomials. See details in Chapter 4 of the book: R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. The following theorem ( in some corrected form) holds Theorem. Let \begin{gather*} ...


3

For such a generating function use this asymptotic expansion of the "digamma function" $\psi$ : $$-\left(\psi\left(\frac 1x\right)+\log x+\frac x2\right)\sim \sum_{n=1}^\infty \frac{B_{2n}}{2n}x^{2n},\quad \text{as}\;x\to 0$$ The origin of this is simply the well known $\;\zeta(1-n)=-\dfrac{B_n}n\;$ applied to the Euler Maclaurin expansion of the harmonic ...


1

Here is a simple derivation of the generating function: start with $$ (1+x)^{-1/2} = \sum_k \binom{-1/2}{k}x^k.$$ Now, \begin{align*} \binom{-1/2}{k} &= \frac{\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\left(\cdots\right)\left(-\frac{1}{2}-k+1\right)}{k} \\ &= (-1)^k \frac{1\cdot 3\cdot 5\cdots (2k-1)}{2^k k!} \\ &= (-1)^k ...


1

Use the binomial theorem. Then $(1-4x)^{-{1 \over 2}} = \sum_{k=0}^\infty \binom{-{1 \over 2}}{k}(-1)^k 4^k x^k$. $\binom{-{1 \over 2}}{k}(-1)^k 4^k = {\prod_{j=0}^{k-1}((-4)(-{1 \over 2}-j)) \over k!} = {\prod_{j=0}^{k-1}(2(1+2i)) \over k!} = {2^k (2k)!\over 2^kk! k!} = \binom{2k}{k}$


2

Starting from the generating function for the harmonic numbers, a generating function for the sequence $\frac{H_{n}}{n}$ may be found as follows: for $z,x\notin[1,\infty)$, $$\begin{align} \sum_{n=1}^{\infty}H_{n}z^{n} &=-\frac{\ln{\left(1-z\right)}}{1-z}\\ \implies \sum_{n=1}^{\infty}H_{n}z^{n-1}&=-\frac{\ln{\left(1-z\right)}}{z\left(1-z\right)}\\ ...


3

Integrate both sides of your identity between $0$ and $t$. You'll get: $$\frac{1}{2}\log^2(1-t)=\sum_{k=1}^{+\infty}\frac{H_k}{k+1} t^{k+1} = \sum_{k\geq 2}\frac{H_{k-1}}{k}t^k.$$ Since $H_{k-1}=H_k-\frac{1}{k}$, by adding $\operatorname{Li}_2(t)$ we are done.


2

First of all, good job on this computation. Everything looks correct, except for your calculation of the residue. Note that \begin{align*} \text{Res}\left(\frac{1}{z(1-t) - x}, \frac{x}{1-t}\right) = \lim_{z \to \frac{x}{1-t}} \left(z - \frac{x}{1-t}\right) \frac{1}{z(1-t) - x} = \frac{1}{1-t} \end{align*} which accounts for the missing factor of ...


0

It should be remarked that the characteristic polynomial of the matrix is $\lambda^3-\lambda^2-10\lambda-5$ just like the characteristic equation for the recurrence for the $P$ values. That is not a coincidence. Also $M_{n+2}=M_{n+1}+10M_n+5M_{n-1}$ and $R_{n+2}=R_{n+1}+10R_n+5R_{n-1}$ The roots are nothing nice, roughly $r_1=3.896,r_2=-2.350,r_3=-0.546$ ...


1

Hint $$\begin{bmatrix} R_{n}\\ M_{n}\\ P_{n} \end{bmatrix}= \begin{bmatrix} 1&0&3\\ 1&0&2\\ 0&5&0 \end{bmatrix}\cdot \begin{bmatrix} R_{n-1}\\ M_{n-1}\\ P_{n-1} \end{bmatrix}$$ let $$A=\begin{bmatrix} 1&0&3\\ 1&0&2\\ 0&5&0 \end{bmatrix}$$ then we only find $A^n$ it is easy to find it ,because ...


0

Looks like we're doing the same challenge ;). So far the best resource I found on this topic is http://oeis.org/A062734 but I'm not sure that the formula/mathematica expression is still valid for n=20 and I have not yet translated it to python. I plan to consult the referenced books, maybe tomorrow.


4

The justification is the identity theorem. If two convergent power series have the same sum in a neighbourhood of $0$, then the coefficients of the two power series are identical. We even have a stronger theorem: Let $$f(z) = \sum_{n=0}^\infty a_n z^n$$ be convergent in $D_r(0) = \{z : \lvert z\rvert < r\}$. If there is a sequence $(z_k)$ in ...


1

You were not accurate enough by omitting the index range in the summation. The generating function is $$0x^0+0x^1+0x^2+1x^3+2x^4+3x^5+4x^6+5x^7=\sum_{n=3}^7(n-2)x^n.$$ The zeroes are accounted for by just omitting the corresponding powers. Note that the following representations are equivalent: ...


0

Your generating function is $x^3+2x^4+3x^5+4x^6+5x^7$ which you can write as $\displaystyle \sum_{n=0}^{5} n x^{n+2}$ $\displaystyle x^2 \sum_{n=0}^{5} n x^{n}$ $\displaystyle \sum_{n=2}^{7} (n-2) x^{n}$ $\displaystyle \left(\sum_{n=0}^{7} (n-2) x^{n}\right) + 2 + x $ $\dfrac{x^3(1-6x^5+5x^6)}{(1-x)^2}$ or as a variety of other things


1

There is a simpler approach. Rewrite the generating function $G_n(x)$ as $$ G_n(x)=(1+x+x^2+x^3)^n = \left(\frac{1-x^4}{1-x}\right)^n=(1-x^4)^n(1-x)^{-n} $$ We want the $x^m$ coefficient of $G_n(x)$. Since $G_n(x)$ is the product of $(1-x^4)^n$ and $(1-x)^{-n}$, we can find this coefficient by finding the series these two are generating functions of, $$ ...


0

For the board that's given, the rook polynomial would be $R(x)=1+6x+7x^2+x^3$, since the coefficient of $x^n$ is the number of ways to place n non-attacking rooks on the board. In addition to direct counting, the rook polynomial can be found by selecting a specific position, such as the third 1 in row 2, and using that the rook polynomial with this ...


3

Note: I think @jayakrishnan provides an interesting reference about the 2-associated Stirling Numbers of the second kind from F.T.Howard. Here's another paper which looks promising. The idea is, that even if it's not exactly the article you have in mind the formulae of $S_2(n,k)$ you will find in the referred papers could be nevertheless valuable and a ...


2

How can we generate a valid $n$-digit code? We can either Take a valid $(n - 1)$-digit code and append an even digit to it. Since there are $5$ ways to choose an even digit, this can be done in $5 \cdot a_{n - 1}$ ways. Take an invalid $(n - 1)$-digit code and append an odd digit to it. Observe that the number of invalid codes of length $n - 1$ is $10^{n - ...


0

The Taylor series of a generating function gives you the coefficients (I guess that's what you mean by "number generated by the generating function) of a generating function. If you're too lazy to work out the expansions by hand, then you can let Wolfram Alpha do the work. After a little of try-and-error you should be able to find coefficients that are in ...


3

I am not sure if this will be helpful or not. You might want to check out the following link, particularly, the reference list in the end : http://www.fq.math.ca/Scanned/18-4/howard.pdf


1

You are right that there are a couple of cases to be considered. You can have 9 zeros and 8 ones, which can be picked in $\binom{17}{9}$ ways. The next case is 10 zeros and 7 ones, which can be picked in $\binom{17}{10}$ ways. I guess you see the pattern. The total number of combinations with more zeros than ones is thus given by \begin{align} \sum_{k = ...


6

Hint: the number of binary sequences with more zeros than ones plus the number of binary sequences with more ones than zeroes plus the number of binary sequences with the same number of ones as zeros is...


0

Hint: $$x^3+2x^4+4x^5+8x^6+\cdots = x^3(1+2x+(2x)^2+(2x)^3+\cdots)$$ Do you know a closed form for the part in parentheses to the right?


0

Actually it is 'easy'. The second generating function is simply $$ G(x,y)=\sum_{k=1}^mkF(x)y^k=\sum_{k=1}^mk\frac{x+x^{k+1} (k x-k-1) }{(x-1)^2}y^k $$ yielding a complicated expression I cannot paste. We get the correct result upon taking the limit $x,y\to1$.


2

Another formula using the powers of $i=\sqrt{-1}$ is $$a_n=\frac{1+i^n+(-1)^n+(-i)^n}{4}.$$ This has to do with the sum of $4$th roots of unity being zero, and the fact that when $n$ is a multiple of $4$ the terms on top are all $1.$


0

$$(1+(-1)^n) \cdot \left(1 + (-1)^{n (1 + (-1)^n)/4}\right)/4$$ But really, is this actually what's requested? This form isn't very useful. If you don't mind complex numbers, to expand on on coffeemath's answer below, in general $\sum_{j=0}^k e^{2\pi i jn/k}$ is $k$ if $k|n$ and $0$ otherwise. In the case $k = 4$ this specializes to $1^n + i^n + (-1)^n + ...


2

Let $C(x)$ be the GF for the sequence $\langle c_n \rangle_{n\ge 0}$, where $c_n$ is the $n^\text{th}$ partial sum of the sequence of squares. If $f(x)$ is the GF for the sequence of squares, then $\frac{f(x)}{1-x}$ is the GF for the sequence of the partial sums of squares. So, we first find the GF for $\langle n^2 \rangle_{n\ge 0}$. Starting from ...


0

$$\sum_{n=0}^\infty \frac{2^8\binom 8n x^n}{2^n}=\sum_{n=0}^8\binom 8n 2^{8-n}x^n =(2+x)^8\qquad \blacksquare$$ OR $$(a+x)^N=a^N\left(1+\frac xa\right)^N\\ =a^N\sum_{n=0}^N \binom Nn \left(\frac xa\right)^n\\ =\sum_{n=0}^\infty a^N\binom Nn \left(\frac xa\right)^n$$ Put $a=2, N=8$: $$(2+x)^8=\sum_{n=0}^\infty 2^8\binom 8n \left(\frac x2\right)^n\qquad ...


2

Hint: $$ \sum \frac{2^8 \binom{8}{n} x^n}{2^n} = \sum 2^8 \binom{8}{n} \left(\frac x2\right)^n = \cdots $$


0

The generating function is $$ g(x)=0+1\cdot x-2x^2+4x^3-8x^4+16x^5-\ldots. $$ Observe that each coefficient starting with the coefficient of $x^2$ is $-2$ times the coefficient of the previous term. This suggests the idea of multiplying $g(x)$ by $-2x$ and subtracting the result from $g(x).$ If you do this, you will find that all terms cancel but one. So ...


0

$$ \left(a_n\right) = (0,~1,-2,~4,-8,~16,~\dots) \wedge n \in \mathbb{N}$$ Let $a_0 = 0$ and forget about it. Now look at modulus of next vales of sequence. 1 2 4 8 16 ... These are the next power of two. So we just have to care about sign. $$\begin{split} a_1 &= &1 = (-1)^0&\cdot 2^0\\ a_2 &= -&2 = (-1)^1 &\cdot 2^1\\ a_3 &= ...


0

Note that: $$\frac{1}{1-x} = 1 + x + x^2 +x^3 + ... + x^n$$ And that: $$x^3*\left(\frac{1}{1-x}\right) = x^3(1 + x + x^2 +x^3 + ... + x^n) = x^3 + x^4 + x^5 +\dots$$ $$x^3 + x^4 + x^5 + \dots +x^8 = x^3(1+ x +x^2 +\dots + x^5)$$ However, since we are only interested in the first $6$ terms (Until $x^5$), we can subtract all the other terms by doing a ...


1

$$A(x)=x^3+...+x^8=x^3(1+...+x^5)=x^3\frac{1-x^6}{1-x}=\frac{x^3-x^9}{1-x}$$


0

Basic idea: [I am solving only part a] a) Let $P(r_1,r_2,...,r_m)$ denote the number of ways n people can pick a total of $r_1$ chairs of type 1, $r_2$ chairs of type 2, . . . $r_m$ chairs of type m such that each person picks one chair. Clearly, $$n=r_1+r_2+...+r_m$$ Claim $$P(r_1,r_2,...,r_m) = {n\choose r_1}*{(n-r_1)\choose ...


1

If $\forall n : a_n > b_n$ then $\forall x > 0$ such that $B(x) < \infty$, $A(x) > B(x)$ and moreover, for all positive $k$, $\frac{d^nA(x)}{dx^n} > \frac{d^nB(x)}{dx^n}$ wherever those derivatives are finite. One possible converse would be that if $\forall x > 0 : A(x) > B(x)$ then $\forall n : a_n > b_n$, but that statement is ...


0

Indeed, it does the trick! B(z) = $A(z) \times \sum\limits_n z^n = \sum\limits_{n} \sum\limits_{k = 0}^n a_k z^n$



Top 50 recent answers are included