# Tag Info

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 ... 0 Using generating functions: Let$P$be the generating function for one Bernoulli trial, i.e. for one$X_i$: we have $$P(s) = q + ps,$$ as the outcome is$X_i = 0$with probability$q$, and$1$with probability$p$. Then the generating function for the sum of$n$trials is $$P(s)^n = (q + ps)^n = \sum_{r=0}^{n}\binom{n}{r}(ps)^r q^{n-r},$$ in which the ... 4 Starting with index$0$this is $${(-1)}^{1+n}\left(\binom{14}{n}-\binom{14}{n-2}\right)$$ (using the fact that$\binom{N}m=0$if$m<0$or$m>N$. 1 The usual way to do this would be to sum each series before you multiply, getting$\frac 1{(1-x)(1-x^2)(1-x^5)}$and expand that, getting$1+x+2x^2+2x^3+3x^4+4x^5+\dots$In your case, I believe the upper limit of the$l$sum should be$k$, not$n$, to get the proper convolution. 1 You say you are looking for an easier way - so set x2=0,1,2,3 and you will get x1=2,4,6,8 respectively (x2>3 doesn't work). The remainder to 12 (10,7,4,1) is to be split between x3 and x4 such that x3≤x4. This yields 14 solutions in total (6+4+3+1). Certainly not the mathematically most beautiful, but the easiest way to solve this question. 1 One way to simplify the computation would be to take out the$\frac{1}{1-x^3}$, so that you only have to do partial fractions on$\frac{1}{(1-x^2)(1-x)}. Then you get \begin{align*} \frac{1}{(1-x^2)(1-x)} &= \frac{1}{4(1+x)} + \frac{1}{4(1-x)} + \frac{1}{2(1-x)^2} \\ &= \frac{1}{4} \sum_{i=0}^\infty (-x)^i + \frac{1}{4} \sum_{i=0}^\infty x^i + ... 2 If you calculateF(0.01)$in Windows calculator you'll get$0.010102030508132134559046368320032$. Look at pairs of digits and you'll see you get the Fibonacci sequence right up until it gets into the 3-digit range. So a simplistic way to do it is to calcuate$F(10^{-5})$to something like 105 digits of accuracy.$F(10^{-5}) \approx 0.00001 00001 00002 ...

4

\begin{eqnarray*} {z\over 1-z-z^2}&=&z\sum_{k=0}^\infty (z+z^2)^k\\ &=&z\sum_{k=0}^\infty z^k(1+z)^k\\ &=&z\sum_{k=0}^\infty z^k \sum_{j=0}^k {k\choose j} z^j\\ &=&\sum_{k=0}^\infty \sum_{j=0}^k {k\choose j} z^{1+j+k} \end{eqnarray*} From this we see that the coefficient of $z^N$ is $$\sum_{j=0}^{N-1}{N-1-j\choose j},$$ in ...

1

First, find the roots of your functions denominator $1-z-z^2$ which are $$z_\pm=-\frac{1\pm\sqrt{5}}{2}$$ Then find the partial fraction decomposition $$\frac{z}{1-z-z^2}=\frac{z}{(z-z_-)(z-z_+)}=\frac{a}{z-z_+}+\frac{b}{z-z_-}$$ which turns out to be $a=\tfrac{1}{2}(1-\tfrac{1}{\sqrt{5}})$ and $b=\tfrac{1}{2}(1+\tfrac{1}{\sqrt{5}})$ Now you can easily ...

3

You can do the following: Solve the equation $1-x-x^2=0$. The roots are $\frac{-1-\sqrt{5}}{2}$ and $\frac{-1+\sqrt{5}}{2}$. Then you have $1-x-x^2=-(x-\frac{-1-\sqrt{5}}{2})(x-\frac{-1+\sqrt{5}}{2})=-(x+\frac{1+\sqrt{5}}{2})(x+\frac{1-\sqrt{5}}{2})$ ...

3

Hint : Subtract the sequence $x^3+x^6+x^9+...$ from $x+x^2+x^3+...$ Both sequences are geometric.

Top 50 recent answers are included