# Tag Info

## New answers tagged generating-functions

4

A number $444\ldots 4$ consisting of $n$ fours is equal to $(10^n-1)\cdot\frac{4}{9}$, see why for yourself. Then the number consisting of $n/2$ fours, then $n/2-1$ eights and then a nine is equal to: $$\frac{4}{9}(10^n-1)+\frac{4}{9}(10^{n/2}-1)+1=\frac{4}{9}(10^n+10^{n/2}+\frac{1}{4})$$ which you can easily see to be equal to: $$(\ ... 2 There are many sequences whose first five terms are 1, 3, 5, 7 and 9. As an example, consider$$a(n) = 5 - \frac{n}{20} (n - 3) (n - 6) ((n - 3)^2 + 4) \text{ for } n=1, \ldots, 5.$$For other possibilities, you can check The On-Line Encyclopedia of Integer Sequences, which has 400+ results for this, including the popular a(n) = 2n+1 similar to the one ... 2 Hint : What is the generating function of :$$f(X):=\frac{1}{1-X} $$Then what is the generating functio for f(\lambda X) if \lambda\in\mathbb{R}. 3.Conclude using the fact that f(-2X) is exactly the function you are looking for. 0 (3-x)+(4-y)+(6-z)=2 So the number of solutions is \large{2+3-1\choose3-1}=6 0 A program in VB to be run in Excel: Sub Macro1546687() ' CONT = 1 ' For I = 0 To 3 For J = 0 To 4 For K = 0 To 6 ' Sum = I + J + K ' If Sum = 11 Then Cells(CONT, 1) = I Cells(CONT, 2) = J Cells(CONT, 3) = K CONT = CONT + 1 End If ' Next K Next J Next I ' End Sub 2 The number of solutions is 6: $$\begin{array} \\ x = 1, & y = 4, & z = 6 \\ \\ x = 2, & y = 3, & z = 6 \\ \\ x = 2, & y = 4, & z = 5 \\ \\ x = 3, & y = 2, & z = 6 \\ \\ x = 3, & y = 3, & z = 5 \\ \\ x = 3, & y = 4, & z = 4 \\ \end{array}$$ Here is some R code that finds the ... 2 Start by setting up your generating function:$$ F(x):=\sum_{n=1}^{\infty}a_nx^n. $$Now, using the recurrence relation that a_n=4a_{n-1}-4a_{n-2}, you can rewrite this as$$ \begin{align*} F(x)&=\sum_{n=1}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}(4a_{n-1}-4a_{n-2})x^n\\ ...

0

$2, 5, 11, 23, 47, \cdots$ Well, I think $a_n = 3 \cdot 2^{n - 1} - 1$ here. OK, let me elaborate a bit. Observe that $d_n := a_{n + 1} - a_{n} = 3 \cdot 2^{n - 1}$. Since $$a_n - a_1 = \sum_{k = 1}^{n - 1} d_{k} = 3 \sum_{k = 1}^{n - 1} 2^{k - 1} = 3 \cdot (2^{n - 1} - 1) = 3 \cdot 2^{n - 1} - 3.$$ Since $a_1 = 2$, we have $a_n = 3 \cdot 2^{n - 1} - 1$.

2

The $n$-th term is $$f(n)=2^n+2^{n-1}-1=3\times 2^{n-1}-1$$ It satisfies the relation $f(n+1)=3\times 2^n-1=2(3\times 2^{n-1}-1)+1=2f(n)+1$ and $f(1)=2$

5

Hint Adding $1$ to each term of the sequence gives $$3, 6, 12, 24, \ldots,$$ and dividing each term of this new series by $3$ gives $$1, 2, 4, 8, \ldots .$$ On the other hand, $1 + x + x^2 + x^3 + \cdots$ is the series for the function $x \mapsto \frac{1}{1 - x}$.

2

The consecutive differences are $3,6,12,\cdots$ So, $T_r-T{(r-1)}=3\cdot2^{r-1}, r\ge2$ Let $T_n=a2^{n+1}+F_n$ $3\cdot2^{r-1}=a2^{r+1}+F_r-\{a2^r+F_{r-1}\}=a2^r+F_r-F_{r-1}$ Set $3\cdot2^{r-1}=a2^r\iff a=\dfrac32$ Can you take it from here?

0

I approached it a little differently. This may not be the most efficient approach, but it worked straightforwardly. Say that a quaternary sequence is good if the first $3$ appears before any $1$ or $2$. Let $a_n$ be the number of good $n$-place sequences that have an even number of $0$s, and let $b_n$ be the number of good $n$-place sequences that have an ...

0

Hint: how can you write $16$ as a sum of $4$'s and $8$'s?

3

mercio's technique (a.k.a. "transfer-matrix method", "dynamical programming") works but is overkill for this question. Here's a simpler way to get the generating function $$A(x) = \sum_{n=0}^\infty a_n x^n = \frac{(1-X)^2}{1-5X+3X^2-X^3}$$ where $X=x^3$ (a natural substitution because clearly $a_n = 0$ unless $n$ is a multiple of $3$). For ...

0

To compute the coefficients $(a_k)$ of your series $\sum_k a_k z^k = (1+z)^n + (1-z)^n$, which make up the numeric function $k \mapsto a_k$ with generating function $f(z) = (1+z)^n + (1-z)^n$, you have just to apply the binomial theorem. We have $$(1 \pm z)^n = \sum_{k=0}^n \binom nk (\pm z)^k = \sum_{k=0}^n \binom nk (\pm 1)^k z^k$$ Adding both, we have ...

1

You can take $E$ to be the species of sets and $E_k$ to be the species of sets of cardinality $k$, so that for any finite set $U$, $E[U]=\{U\}$ and $$E_k[U]=\begin{cases} \{U\},&\text{if }|U|=k\\ \varnothing,&\text{otherwise}\;. \end{cases}$$ Thus, if $a_n=|E[n]|$ is the number of $E$-structures on $n$ elements, and $b_n=|E_k[n]|$ is the number of ...

1

Let $T$ be a $t$-ary tree, and suppose that $T$ has $m$ nodes. Each node except the root has a unique parent, and that parent is an internal node. Let $V_0$ be the set of all non-root nodes, and let $V_i$ be the set of internal nodes; the map that takes a node to its parent is a $t$-to-$1$ map from $V_0$ onto $V_i$, so $|V_0|=t|V_i|$. If $T$ has $n$ internal ...

1

I've came up with this solution. Can someone check if it is correct? Since $(1+z)^\alpha=\sum_{n \geq 0}\binom{\alpha}{n}z^n$, it follows that: $$(1-5z)^{-\frac{1}{2}}=\sum_{n \geq 0} \binom{-\frac{1}{2}}{n}(-5)^nz^n$$ Putting it to the original formula, we get: $$2\sum_{n \geq 0} \binom{-\frac{1}{2}}{n}(-5)^nz^n + 3\sum_{n \geq 0} ... 3 Hint: We have, by the usual formula for the sum of a finite geometric progression, that if x\ne 0 then$$1+x+x^2+\cdots+x^6=\frac{1-x^7}{1-x}.$$It follows that$$(1+x+x^2+\cdots+x^6)^4=(1-x^7)^4(1-x)^{-4}.$$Note that we only need two easy terms of the expansion of (1-x^7)^4. 3 Hint: think of a as corresponding to x^a in 1+x+x^2+\ldots+x^9, and similarly for b,c,d. Then the number of solutions will be the coefficient of x^{25} in (1+x+x^2+\ldots+x^9)^4. Also note that$$1+x+x^2+\ldots+x^9 = {1-x^{10} \over 1-x}.-3 The n-th Taylor coefficient of a function f in the neighborhood of a point z_{0} is \frac{1}{n!}\frac{d^{n}}{dz^{n}}f(z)|_{z_{0}}. Use a computer algebra system to calculate this closed form coefficients. 0 In general: \begin{align} \left( \sum_{n \ge 0} a_n z^n \right) \cdot \left( \sum_{n \ge 0} b_n z^n \right) = \sum_{n \ge 0} \left(\sum_{0 \le k \le n} a_k b_{n - k} \right) z^n \end{align} In your particular case, a_n = 1, switching the product around: \begin{align} \left( \sum_{n \ge 0} b_n z^n \right) \cdot \left( \sum_{n \ge 0} ... 1 f(x)=\frac{1}{1-x}, g(x)=\frac{1}{1-2x}, f(x)g(x)=\frac{1}{(x-1)(2x-1)} 2 You want the Cauchy product: the coefficient of x^n in f(x)g(x) is\sum_{k=0}^na_kb_{n-k}=\sum_{k=0}^n1\cdot2^{n-k}=\sum_{k=0}^n2^{n-k}=\sum_{k=0}^n2^k=2^{n+1}-1=c_n\;.$$The generating function is simply f(x)g(x); are the generating functions f(x) and g(x)? 1 HINT: Notice that k^2+3k+2=(k+2)(k+1). Let a_k=(k+2)(k+1) and b_k=1. Then$$\sum_{k=0}^n(k+1)(k+2)=\sum_{k=0}^na_kb_{n-k}\;,$$which is the coefficient of x^n in$$\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)\;.$$To get the generating function for \sum_{n\ge 0}a_nx^n you can use the observation that (k+2)(k+1)x^k is the ... 2 You have for m\geq 1$$\sum_{j=0}^m {m \choose j} A_j=-A_m$$This gives that with \displaystyle f(x)=\sum_{k=0}^{+\infty}\frac{A_j}{j!} x^j, if we multiply by x^m and sum for m\geq 1, we have$$f(x)\exp(x)-1=-(f(x)-1)$$hence \displaystyle f(x)=\frac{2}{\exp(x)+1}. Now we find easily that f(x)+f(-x)=2, and we are done. 1 Method 1: Let$$S(x) = \sum_{n\geq 0} \frac{x^{n}}{n+1}then \begin{align} D_{x}\left( x \, S(x) \right) = \sum_{n\geq 0} x^{n} = \frac{1}{1-x} \end{align} which leads toS(x) = - \frac{\ln(1-x)}{x}.Now \begin{align} \sum_{n=1}^{\infty} a_{n} \, t^{n} &= \sum_{n=1}^{\infty} \sum_{k=1}^{n-1} \frac{1}{k(n-k)} \, t^{n} \\ &= \sum_{n=1}^{\infty} ... 0 Hint: \frac{1}{n}(\frac{1}{n-k}+\frac{1}{k})=\frac{1}{k(n-k)} 2 The expression [z^n]\frac{2+3z^2}{\sqrt{1-5z}} $$means "The coefficient of z^n in the Maclaurin series for \frac{2+3z^2}{\sqrt{1-5z}}." For example,$$ \frac{2+3z^2}{\sqrt{1-5z}} = 2 + 5z + \frac{87}{4}z^2 + \frac{685}{8}z^3 + \cdots, $$so$$ [z^3]\frac{2+3z^2}{\sqrt{1-5z}} = \frac{685}{8}. $$1 I would prefer complex variables for this one but it can be done using generating functions only. We have for the LHS that it is$$\sum_{r=1}^n n {n-1\choose r-1} {m\choose r} = n \sum_{r=0}^{n-1} {n-1\choose r} {m\choose r+1}.$$Note that when m-1\gt n-1 we can extend r to m-1 because the first binomial coefficient is zero then. And when m-1\lt ... 1 There is an undocumented constructor combstruct/Theta which can be used to signify pointing. It is the reification of x \frac{d}{dx} to the level of grammars. It is not fully supported, but worked in the examples I tried. 4 Count all the way to tile a rectangle without identifying symmetric patterns first. For each subset S of a 4 \times 2 rectangle, consider the number a_{S,n} of ways to tile a 4 \times n rectangle with the squares in S removed on the left border of the rectangle. Focus on the squares that are still on the leftmost column, consider all the ways to ... 0 It looks as if you may not have had much experience with this yet, so I’m going to write this out as a fairly complete solution. I prefer to use the following technique. First, shift the index of the recurrence to get a_n on the lefthand side: a_n=a_{n-1}+n^2. Then make an adjustment so that the recurrence is correct for all integers n\ge 0 if we ... 1 Start with \sum z^n = \dfrac{1}{1-z} 1) Multiply both sides by z 2) Differentiate 3) Multiply by z 4) Differntiate 0 Recall:$$S(z) = \sum_{n=0}^\infty z^{n} = \frac 1{1-z}\ \ \text{for }|z|< 1$$Your summation is equivalent to:$$\frac{d}{dz}\left(z\cdot\left(\frac{d}{dz}\left(z\cdot S(z)\right)\right)\right) = \frac d{dz}\left(z\cdot \left(\sum_{n=0}^\infty(n+1)z^n\right)\right) = \frac d{dz}\left(\sum_{n=0}^\infty(n+1)z^{n+1}\right) = ...

0

HINT Assuming $$G(x) = \sum_{n=0}^\infty z_n x^n$$ converges, then $$G'(x) = \sum_{n=1}^\infty n z_n x^{n-1}$$ in the radius of convergence.

0

Alright so $a_k = (F_k)^2 \forall k$ So the intial conditions are quite simple $a_0 = (F_0)^2 = 0$ and $a_1 = (F_1)^2 = 1$. Now the actual proof. $a_{n+3} = (F_{n+3})^2=(F_{n+2}+F_{n+1})^2 = F_{n+2}^2 +F_{n+2}F_{n+1} +F_{n+2}F_{n+1} + F_{n+1}^2 = a_{n+2} + ... 0 Generating functions are functions for whom the coefficients of the taylor series expansions match up with some discrete combinatorics problem. They are useful in the field of Analytic Combinatorics, where one uses complex analysis to generate asymptotic approximations for large values...for instance, it can be hard to compute a combinatorics problem when ... 1 You know that$F_{n+3} = F_{n+2} + F_{n+1}$. So you have:$F_{n+3}^2 = F_{n+2}^2 + F_{n+1}^2 + 2F_{n+2}F_{n+1}$. Then notice that$F_{n+2} = F_{n+1} + F_n$, so you get$F_{n+3}^2 = F_{n+2}^2 + F_{n+1}^2 + 2F_{n+1}F_n + 2F_{n+1}^2 \Rightarrow F_{n+3}^2 - F_{n+2}^2 - 2F_{n+1}^2 = F_{n+1}^2 + 2F_{n+1}F_n$Then add$F_n^2$to both parts of this equality: ... 0 I recommend you look at the Goulden-Jackson cluster method. See, for example, this answer, which contains references. 0 I prefer the notation$n\brace k$for your$S(n,k)$. The first step is to observe that${n\brace 1}=1$for$n\ge 1$: there is only one partition of$[n]=\{1,\ldots,n\}$into just one part. Thus, $$F_1(x)=\sum_{n\ge 1}{n\brace 1}x^n=\sum_{n\ge 1}x^n=x\sum_{n\ge 1}x^{n-1}=x\sum_{n\ge 0}x^n=\frac{x}{1-x}\;.$$ To get$F_2(x)$, we need to figure out what ... 2 Suppose we seek to verify that $$B_n(qx) = q^{n-1} \sum_{j=0}^{q-1} B_n\left(x+\frac{j}{q}\right).$$ The EGF of the LHS is $$\frac{t e^{qxt}}{e^t-1}.$$ The EGF of the RHS is $$q^{n-1} \frac{t e^{xt}}{e^t-1} \sum_{j=0}^{q-1} e^{tj/q} = q^{n-1} \frac{t e^{xt}}{e^t-1} \frac{e^t-1}{e^{t/q}-1} \\ = q^{n-1} \frac{t e^{xt}}{e^{t/q}-1}.$$ The coefficients ... 0 A hint: Using$A(x)=\sum_{n\geq1} a_n x^n$compute the power series of$A^2(x)$. 0 You seem to have done all the necessary work, but confused a couple things. The Taylor series should be evaluated about the point$x=0$, not about the first terms of the sequences$a_0=1$,$b_0=0$. In other words, the$n^{\rm th}$derivatives of$f$and$g$that you computed with partial fractions should be evaluated at$0$, and then you can use Taylor's ... 2 Hint: $$2^{0}+2^{0}x+2^{1}x^{2}+2^{1}x^{3}+2^{2}x^{4}+2^{2}x^{5}+2^3x^6+2^3x^7\cdots=$$$$\left[1+2x^{2}+\left(2x^{2}\right)^{2}+(2x^2)^3+\cdots\right]+x\left[1+2x^{2}+\left(2x^{2}\right)^{2}+(2x^2)^3+\cdots\right]$$ 0 Let$(a_n)$be the sequence you submitted to us. Let$A$be the GF associated. We have : $$A=\sum_{n=0}^{\infty}2^{\lfloor \frac{n}{2}\rfloor }X^n$$ now instead of summing over$n$we sum over$k=\lfloor \frac{n}{2}\rfloor$: $$A=\sum_{k=0}^{\infty}2^{k}X^{2k}+2^{k}X^{2k+1}$$ Finally we divide the sum into two parts : ... 1 As I wrote in a comment, the expression at the top should be divided by$n!$and then becomes$\sum_{i=0}^n\frac1{i!}\binom ni$. To get this from the expression at the bottom, exchange the order of summation and apply the hockey stick identity. 1 The problem with using five$(1+x+x^2+x^3+x^4+x^5)^5$is that you get duplicated partitions in that way. For instance$4+3+5=12$and$3+5+4=12$gives in fact the same partition. The intuition behind the solution is that,$z_1$represent the number of$1$s in the partition, then$z_2$represent the number of$2s in the partition and so on, in this way the ... 1 Note: Please note, this is essentially the same as Marko Riedels answer. Here we simply avoid the integral notation which might be somewhat more convenient. In order to calculate OPs sum it's beneficial to consider the more general expression \begin{align*} S_n=\sum_{s= 0}^{\lfloor\frac{n}{2}\rfloor}(-1)^s\binom{3n-2s}{2n}\binom{2n+1}{s} ... 2 Suppose we seek to evaluate $$S_n = \sum_{q=0}^n (-1)^q {6n-2q\choose 4n} {4n+1\choose q}.$$ Introduce $${6n-2q\choose 4n} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n-2q+1}} \frac{1}{(1-z)^{4n+1}} \; dw.$$ This is zero whenq\gt n$so we may extend the summation to infinity to obtain$\$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2n+1}} ...

Top 50 recent answers are included