# Tag Info

0

Let $z=4^u$ , Then $G(4\times4^u)=\dfrac{G(4^u)}{2\times4^u}$ $G(4^{u+1})=\dfrac{G(4^u)}{2\times4^u}$ $G(4^u)=\prod\limits_u\dfrac{1}{2\times4^u}$ $G(4^u)=2^{-u}4^{-\sum\limits_uu}$ $G(4^u)=\Theta(u)2^{-u}4^{-\frac{u(u-1)}{2}}$ , where $\Theta(u)$ is an arbitrary periodic function with unit period $G(4^u)=\Theta(u)2^{-u^2}$ , where $\Theta(u)$ is an ...

0

Good question! For one thing, any power series $$f(x) = \sum_n a_n (x-a)^n$$ may be converted into a power series based around $0$ by taking $$g(x) = f(x+a) = \sum_n a_n x^n.$$ and power series of this form are more convenient to work with. For example, we frequently want to multiply generating functions, but how should we interpret a product of power ...

2

we can prove this limit $$\lim_{n\to\infty}\dfrac{\log^2{n}}{n}\sum_{k=2}^{n-2}\dfrac{1}{\log{k}\log{(n-k)}}=1$$ This is a International Competition in Mathematics for Universtiy Students in Plovdiv, Bulgaria 1994 last problem: can see this solution:http://www.imc-math.org.uk/imc1994/prob_sol.pdf

0

There's a nice simplification: define a related triple $(d_1, d_2, d_3)$ by \left\{ \begin{align} d_1 &= e_1 - 10 \\ d_2 &= e_2 - 1 \\ d_3 &= e_3 - 20 \end{align} \right. Then you have the system of equations and inequalities: \begin{align} d_1 + d_2 + d_3 &= 16 \\ 0 \le d_1 &\le 15 \\ 0 \le d_2 &\le 14 \\ 0 \le d_3 &\le ... 0 Using the lower bounds, write e_1 = 9 + f_1, similarly e_2 = f_2 and e_3 = 19 + f_3. Then you want positive-integer solutions to f_1 + f_2 + f_3 = 19 with f_1 \le 16, f_2 \le 15, and f_3 \le 26. The last of these is redundant (as f_3 \le 19-2 in any case), so drop it. The number of positive-integer solutions to f_1 + f_2 + f_3 = 19 is ... 1 For the first step Every n_i can have a value 1,2,.. so the generating function for this n_i is \sum_r rx^r. So look at (\sum_r rx^r)^k $$If you look to the coefficient of x^n then you have n_1+...+n_k=n because of the exponents and as coefficients it has$$ \sum_{n_1+...n_k=n}n_1\cdot...\cdot n_k $$I hope this makes it understandable. 1 I think something goes wrong with your A and B. I think you should want to use the "fraction method" like$$ \frac{1}{(1-x)^2(1+x)}=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{1+x} $$And find A,B,C that help. But when you have f_1f_2=(x^2+x^3+x^4+...)(x^0+x^2+x^4+...). You want the coefficient of the term x^{100}. For every x^k in f_1 there is ... 2 First, note that$$\frac{{5x - 3{x^2}}}{{{{(1 - x)}^3}}} = \frac{3}{(x-1)}+\frac{1}{(x-1)^2}-\frac{2}{(x-1)^3}$$And,$$\frac{3}{(x-1)} = \sum \limits_{k=0}^{\infty}(-3)x^k\frac{1}{(x-1)^2}= \sum \limits_{k=0}^{\infty}(k+1)x^k\frac{-2}{(x-1)^3}= \sum_{k=0}^{\infty} x^k(k+1)(k+2)$$Add them up and you get$$\sum \limits_{k=1}^{\infty} ...

1

I think you're overthinking things. First of all, \begin{align*} 5 {k + 1 \choose 2} - 3{k \choose 2} &= 5\frac{(k+1)k}{2} - 3\frac{k(k-1)}{2} \\ &= \frac{5}{2} k^2 + \frac52 k - \frac32k^2 + \frac32 k \\ &= 4k + k^2 \\ &= k(k + 4) \\ \end{align*} So your sequence is $a_k = k(k+4)$. Second of all, they probably want you to plug in $k = 0$ ...

0

As long as you're working on these types of problems in Wilf's book, you might also want to read a truly wonderful article by Noonan and Zeilberger on the Goulden-Jackson cluster method. It generalizes the above problem to avoid any collection of words (not just $k$ 1's in a row), and the method is no more complex than your calculation.

0

I assume your question is about the probability generating function of a discrete random variable $X$ taking nonnegative integer values, defined as $$G_X(t) = E(t^X) = \sum_{k \ge 0} \Pr(X = k)\, t^k.$$ Your second question on why $G_X(1) = 1$ is easy to answer: when $t=1$, we have $$G_X(1) = E(1^X) = E(1) = 1$$ as $1^X$ is always $1$ no matter what the ...

2

First of all, some unsolicited advice: your derivation for (b) need not be so messy. It greatly simplifies things to observe that $$f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,m-k,k) \tag{1}$$ holds not just when $0 \le k \le m \le n$, $k < n$. In fact, it holds for any $n \ge 0, m \ge 0, k \ge 1$, except in the two cases $m = n = k$, and $m = n = ... 0 One solution is:$G(z) = k z^{\displaystyle{-(1+\ln(z)/\ln(16))}}$I discovered this by considering how the logs of both sides of the function scale. 2 $$f(x)=\frac{2}{1-2x}=2\sum_{k=0}^\infty 2^k x^k=2+2^2x+2^3x^2+\cdots$$ 2 If the contestants are all distinct, you can take account of that by changing your coefficients: Of the$5$entrants from each state, there are$\binom{5}{0}$ways to choose 0 of them,$\binom{5}{1}$ways to choose$1$,$\binom{5}{2}$ways to choose$2, and so on. So, the generating function for contestants from a single state is $$... 1 The generating function for the Central Binomial Coefficients is$$ \sum_{k=0}^\infty\binom{2k}{k}x^k=(1-4x)^{-1/2}\tag{1} $$Integrating (1) and dividing by x yields$$ \sum_{k=0}^\infty\binom{2k}{k}\frac{x^k}{k+1}=\frac{1-\sqrt{1-4x}}{2x}\tag{2} $$Sum the formula against x^m:$$ \begin{align} ... 1 Whenn=1$it's easy to evaluate for all$m\ge1$. Then it's easy to prove the$n+1$by induction, given the$n$case (for all$m$): just write $$\binom{n+k}{m+2k} = \binom{n-1+k}{m+2k} + \binom{n-1+k}{m-1+2k}.$$ 0 I don't know whats going on but the question's title is provoking laymen. Stirling numbers(1st kind)$ 1, 1+1/2, 1+1/2+1/3, 1+1/2+1/3+1/4, ..... $after computing lcm gives Stirlings in the numerators and factorial in the denominators. 1$F_0 = 0$,$F_1 = 1$, and$F_{n+2} = F_n + F_{n+1}$.$F_{n+3} = F_n + 2F_{n+1}F_{n+6} = 5F_n + 8F_{n+1} = F_n + 4F_{n+3}$Let G be a series where$G_0 = 0$,$G_1 = 2$, and$G_{n+2} = G_n + 4G_{n+1}$. In other words,$G_i = F_{3i}$. Its generating function is$g(x) = \dfrac{2x}{1 - 4x - x^2}$.$\sum_{n \ge 0}F_{3n}2^{-3n} = \sum_{n \ge 0} ...

1

Here's an approach via generating functions. As the Fibonacci recurrence is defined by $F_{n+2} = F_{n+1} + F_n$, we have $$\sum_{n \ge 0} F_{n+2}z^{n+2} = \sum_{n \ge 0} F_{n+1}z^{n+1}z + \sum_{n \ge 0}F_nz^nz^2$$ which with the generating function $G(z) = \sum_{n\ge0} F_n z^n$ gives $$G(z) - F_0 - F_1z = zG(z) - zF_0 + z^2G(z)$$ and therefore (using $F_0 = ... 3 The middle expression is the result of iterated use of the power rule. If you take the$n^\text{th}$(formal) derivative of$\frac1{1-x}$, you end up with$\frac{1}{(1-x)^{n+1}}$times some polynomial in$n$. If you then take the fifth derivative of the geometric series, then you can work out the coefficient to be$\binom{n+5}{5}$but missing some terms; ... 2 As suggested, the simplest would consist in a use of Binet formula for Fibonacci number. It write $$F_n=\frac{\varphi ^n-\psi ^n}{\sqrt{5}}$$ with$\varphi=\frac{1}{2} \left(1+\sqrt{5}\right)$and$\psi=\frac{1}{2} \left(1-\sqrt{5}\right)$. So, if we consider each term of the sum, we can rewrite it as $$F_{3n}2^{-3n}=\frac{\Phi ^n-\Psi ^n}{\sqrt{5}}$$ ... 1 For someone who may need this. \begin{equation*} \begin{split} d(x) &= (4-2x+x^2)^{-1} \\ &= \frac{1}{(\alpha -x)(\beta -x)}\\ &= \frac{A}{\alpha -x} + \frac{B}{\beta -x} \end{split} \end{equation*} We can determine that : \begin{equation*} A(\beta -x) + B(\alpha -x) = 1 \end{equation*} So, we have: \begin{equation*} A = \frac{1}{\beta - ... 1 Alf van der Poorten, wrote about this, calling it the "Hadamard product" of the two generating series. It's not easy stuff, but you can read about it in section 8 of this paper. See the example in Section 11, where $$\sum{2h\choose h}x^h=(1-4x)^{-1/2}$$ is an elementary and algebraic function, but $$\sum{2h\choose h}^2x^h$$ is a complete elliptic integral ... 1 The strategy is to look for the generating function $$G(x,y)=\sum_{n,m}F(n,m)x^ny^m.$$ To do so: Multiply by$x^ny^m$each term in the identity, getting $$F(n,m)x^ny^m = n\cdot F(n-1,m) x^ny^m+ (n-m)\cdot F(n-1,m-1)x^ny^m.$$ The LHS terms sum to the generating function$G(x,y)$. For the first terms on the RHS, use the identity $$... 1 Determining the asymptotic growth of the coefficients of a generating function is essentially the entire subject of Analytic Combinatorics, on which see the 810-page book by Flajolet and Sedgewick available online. The basic setup is this: for a large class of generating functions G(z) = g_0 + g_1z + g_2z^2 + \dots, we can show that the coefficients ... 1 By the Cauchy-Hadamard theorem, \limsup\sqrt[n]{|a_n|}=1/R. If the lim sup is in reality a lim, and even better, if the limit of the quotient formula exists, then the asymptotic growth rate is about the reciprocal of the distance of the origin to the closest singularity of f. 1 I presume that in$$G(z) = a_0 + a_1 z + a_2 z^2 + \dots,$$a_k represents the probability that a certain discrete random variable (call it X) takes the value k, for each k. For the mean E[X] defined as E[X] = a_0(0) + a_1(1) + a_2(2) + a_3(3) + \dots, we can differentiate to get$$G'(z) = a_1 + 2a_2z + 3a_3z^2 + 4a_4z^3 + \dots,$$whose value ... 1 I'm guessing your recurrence is: a_n -7a_{n-1} +10a_{n-2}=0 \longleftrightarrow a_n = 7a_{n-1}-10a_{n-2} \longleftrightarrow a_{n+2} = 7a_{n+1} -10a_n . Let's say a_0=0, a_1=1 for sake of example. Set F(x) = a_0 + a_1x + a_2x^2+\ldots = \sum_{n=0}^{\infty} a_nx^n So \frac{F(x) - a_0}{x} = a_1 + a_2x + a_3x^2+\ldots =\sum_{n=0}^{\infty} ... 2 Solution I. Introduce the sequences a_{n,k} and b_{n,k} that count the number of k element-subsets of n that contain no consecutive integers where the a_{n,k} count such sequences that do not use n and the b_{n,k} the ones that do use n. Then we clearly have$$a_{n,1} = n-1 \quad\text{and}\quad b_{n,1} = 1.$$Furthermore we have the ... 2 The combinatorial species here seems to be$$\mathcal{T} = \mathcal{Z} + \mathcal{Z}(\mathfrak{M}_1(\mathcal{T}) + \mathfrak{M}_2(\mathcal{T})).$$This is one of several interpretations of the question. The one we chose here is that the trees are not labelled and two trees that differ only in the left and right children being exchanged are considered the ... 0 The Coefficient of x^9 in \displaystyle(1+x^3+x^8)^{10}=[(1+x^3)+x^8]^{10}=(1+x^3)^{10}+\binom{10}1(1+x^3)^9x^8+\cdots+(x^8)^{10} = the Coefficient of x^9 in \displaystyle (1+x^3)^{10}+10x^8(1+x^3)^9 Now, the Coefficient of x^9 in \displaystyle(1+x^3)^{10} is \displaystyle\binom{10}3 and the Coefficient of x^9 in ... 1 Every term in the expansion of (1+x^3+x^8)^{10} is of the form 1^a(x^3)^b(x^8)^c with a+b+c = 10. It is clear that the only way to get x^9 as a term is when a = 7,b=3,c=0. And the coefficient corresponding to this term is the number of ways you can choose three x^3's from 10 i.e \binom{10}{3} 0 Hint: Solve for integer solutions to 9 = 8a + 3b + 0c subject to a+b+c = 10. 0 For sure, what lab bhattacharjee gave is the answer. However, before starting, you could have simplified your problem since$$\frac{\left(1-x^6\right)^4}{(1-x)^4} = \left(x^5+x^4+x^3+x^2+x+1\right)^4$$and the problem becomes simpler. 1 So, the coefficient of x^{12} = the coefficient of x^0 in (1-x^6)^4 \cdot the coefficient of x^{12} in (1-x)^{-4} +the coefficient of x^6 in (1-x^6)^4 \cdot the coefficient of x^{12-6} in (1-x)^{-4} +the coefficient of x^{12} in (1-x^6)^4 \cdot the coefficient of x^{12-12} in (1-x)^{-4} ... 0 You can determine a function that simultaneously "generates" both sin(nt) and cos(nt). If you assume x to be real, then you're looking for the imaginary part of the coefficient of \frac{x^n}{n!} in the following expression.$$ \sum_{n=0}^\infty \left(cos(nt) + i.sin(nt)\right)\frac{x^n}{n!} \\ = \sum_{n=0}^\infty e^{int}\frac{x^n}{n!} \\ = ... 0 Here's a way. The number of$l$-step walks from$(0,\cdots,0)$to$(u_1,\cdots,u_n)$will be $$[x_1^{u_1}\cdots x_n^{v_n}](x_1+\cdots+x_n)^l \tag{\cdot}$$ where the polynomial is considered an element of$\Bbb Z[x_1,\cdots,x_n]/(x_1^2-1,\cdots,x_n^2-1)$. We can decompose$[x_1^{u_1}\cdots,x_n^{u_n}]=[x_1^{u_1}]\cdots[x_n^{u_n}]$informally and consider ... 0 I'll start writing down my approach. I don't know yet whether it will work out or not, but at least you can see it and maybe continue it. There are$n$dimensions. For each move, we choose a direction$1\leq i\leq n$(north/south, east/west, up/down and so on for higher dimensions) and move in that direction. In vector notation:$a_0=(0,0,\dots,0)$, ... 0 I'm taking a Discrete Mathematics course right now, using Applied combinatorics by Roberts and Tesman. It does have some good 'real life' examples and applications. 0 Just Cauchy's product followed by some cleanup. 2 I've been thinking of this problem on and off for more than a day, and at the end the answer I've reached is very trivial and already implicit in your calculations. Specifically, it's just this simple fact: Lemma: If a number$A$has$n$digits, then for$m > n$, the number$A(10^m - 1)$has a run of$m-n$nines, namely in the positions having place ... 1 Not a generating function approach, but I would just calculate how many numbers there are. The digits will appear in their proper proportion ($\frac 1{45} 1's, \dots \frac 9{45} 9's$), so if there are$N$numbers the sum will be$\frac N{45}(1^2+2^2+\dots 9^2)(\frac {10^{45}-1}9)$where the last factor is the number with$45\ 1's$To evaluate$N\$, we can ...

Top 50 recent answers are included