# Tag Info

6

With a telescoping sum: note that $$(k+1)^4-k^4= 4k^3+6k^2+4k+1.$$ Write this equation for $k=1, 2,\dots, n$ and add them. You'll need to know the sums $1+2+\dots +n$ and $1^2+2^2+\dots +n^2$, which are standard.

4

Here is some information for odd $k=2K+1$ regarding a more symmetric representation which could be somewhat easier to show. A similar approach might work for the even case. We split \begin{align*} \sum_{l=1}^{2K}&\frac{(-1)^l}{l}\sum_{m=1}^{\min\{l,2K+1-l\}}\binom{l}{m}\binom{2K-l}{m-1} \sum_{c=0}^m\binom{m}{c}\binom{2K+1-2m}{i+j-2c-l}\binom{m}{l+c-i}\\ &...

4

Let $S_n^{(r)}=\sum_{k=1}^n k^r$. Note that $$(k+1)^4-k^4=4k^3+6k^2+4k+1$$ and after summing for $k=1,\dots,n$, (the sum on the left is telescopic) we get $$(n+1)^4-1=4 S_n^{(3)}+6S_n^{(2)}+4S_n^{(1)}+n.$$ In a similar way, $$(k+1)^3-k^3=3k^2+3k+1\implies (n+1)^3-1=3S_n^{(2)}+3S_n^{(1)}+n$$ and $$(k+1)^2-k^2=2k+1\implies (n+1)^2-1=2S_n^{(1)}+n.$$ Now ...

3

Here are two references which might be useful when learning recurrence relations. Some interesting techniques are presented in Mathematics for the Analysis of Algorithms by D. E. Knuth and D. H. Greene. One of them is the so-called repertoire method. A real life application is presented in this post . Recurrences are also a prominent theme in ...

3

You've used the denominator of $\frac{1+x}{1-x^2-2x^3}$ to get the recurrence: the numerator gives the initial terms. If we generalise slightly so that you can see the derivation, $$\frac{b+cx+dx^\alpha}{1-x^2-2x^3}$$ gives recurrence $$a_n=a_{n-2} + 2a_{n-3} + b[n = 0] + c[n = 1] + d[n = \alpha]$$ where $[\cdot]$ is an Iverson bracket and evaluates to $1$ ...

3

If you'll grant me that $f(n)=\sum_{k=0}^n k^3=an^4+bn^3+cn^2+dn+e,$ then we have this system to solve: $$f(0)=0=e\\ f(1)=1=a+b+c+d+e\\ f(2)=9=16a+8b+4c+2d+e\\ f(3)=36=81a+27b+9c+3d+e \\ f(4)=100=256a+64b+16c+4d+e.$$ From this it follows that $e=0$ and $$9-2\times1=7=14a+6b+2c\\ 36-3\times1=33=78a+24b+6c\\ 100-4\times1=96=252a+60b+12c$$ Now can you ...

3

Recall the classic Cayley's Result that there are $n^{n-2}$ labelled tree on $n$ vertices. https://en.wikipedia.org/wiki/Cayley%27s_formula Choose one of the vertices of a labelled tree and call it the (first) root ($r_1$); it is clear that there are $n^{n-1}$ rooted trees. Next choose a second vertex ($r_2$) (possibly the same as the first) and call it ...

3

It is well-known that $$e^x = \sum_{a=0}^\infty \frac{x^a}{a!}.$$ This implies that $$(e^x-1)^k = \sum_{n=0}^\infty B(n,k) x^n.$$ It is also known that $$\ln (1+x) = -\sum_{k=1}^\infty (-1)^k \frac{x^k}{k}.$$ Therefore $$\ln (1 + (e^x-1)) = -\sum_{k=1}^\infty (-1)^k \frac{(e^x-1)^k}{k} = -\sum_{k=1}^\infty \sum_{n=0}^\infty (-1)^k \frac{B(n,k) x^n}{k}=... 3 You have to be careful with the first term of the series. I think F(x)=3xF(x)+\frac x {1-x}. 2 While there's a lot of ways to find a closed form for combinatoric sums (including the most practical one of looking the terms up in OEIS, as Claude Leibovici had), I'd like to remind the more general way of using generalized hypergeometric functions. Even though the sum is finite, we can easily treat it as a particular case of hypergeometric series.$$a_n(...

2

Computing for the first terms, the numbers are $$\{1,2,4,10,26,76,232,764,2620,9496,35696,140152,568504,2390480,10349536\}$$ This is sequence $A000085$ at $OEIS$. They seem to be somehow related to restricted Stirling numbers of the second kind. Looking at the page, you will find soem interesting asymptotics.

2

The coefficient of $x^{12}$ is equal to the number of partitions of $12$ in which all summands are even. Given a partition of $12$ in which all summands are even we can divide each summand by $2$ to get a partition of $6$. And given a partition of $6$ we can find a partition of $12$ with even summands by doubling each summand. So there is a one-to-one ...

2

I still think the way you go is as good as one gets. Precisely, if $$\color{darkblue}{F_m(z)}:=\sum_{p\geqslant 0}\binom{mp}{p}\frac{z^p}{(m-1)p+1}\color{darkblue}{=1+z\big(F_m(z)\big)^m}\tag{1}$$ (the equality is from here, where $F_m(z)=B_{m,1}(z)$ in that notation), then $$\color{darkblue}{B_m(z)}=F_m(z)+(m-1)zF_m'(z)\color{darkblue}{=\frac{F_m(z)}{m-(m-1)... 2 Too long for a comment. It is advantageous to write your quantity as:$$ c_{ij}^k =k\sum_{\ell=1}^{k-1}\sum_{m=0}^{\ell}\sum_{c=0}^m\frac{1}{\ell} \left(-1\right)^{\ell-i} \binom{\ell}{m}\binom{k-\ell-1}{m-1}\binom{m}{c} \binom{k-2m}{i + j -2c -\ell}\binom{m}{\ell+c-i}, $$where k is assumed to be larger than 1. According to numerical experiments the ... 2 To use a generating function to solve this, it helps to know that the ordinary generating function for the sequence \{n^m\}_{n=0}^\infty is \left(x\frac d{dx}\right)^m\frac1{1-x}: differentiation multiplies the coefficient of x^n by n and shifts the sequence down, and multiplying by x shifts back up and sets the constant term to 0, so the net ... 2$$\frac{1}{1-\alpha}=\sum_{n=0}^\infty \alpha^n$$is the foundation. Apply with \alpha=6x^2 and we get$$\frac{1}{1-6x^2}=\sum_{n=0}^\infty (6x^2)^n = \sum_{n=0}^\infty 6^n x^{2n}$$so this corresponds to the sequence 1, 0, 6, 0, 36, \ldots, or in a formula$$a_n = \begin{cases} 0 & n \text{ odd }\\ 6^{\frac{n}{2}} & n \text{ even } \end{...

2

Taking a cue from lulu above, let's work through a smaller example: making 10 cents out of change. You can either include a dime (10 cent coin), or not. If you use a dime, that's it, you're done. If you don't use a dime, you can use 0, 1 or 2 nickels (5 cent coins). Whichever option you choose, you are forced to fill up the remainder with single cent coins. ...

2

By way of an extended comment in response to a pers. comm. / request. A conjectured alternate representation of the sum (here $i=p$ and $j=q$) is given by $$k (-1)^p \mathrm{Res}_{z=0} z^{p-1} [w^{p+q}] (1+w)^{k} [v^{k}] (1+v)^{k-1} \\ \times \sum_{\ell\ge 1} \frac{(-1)^\ell}{\ell} z^{-2\ell} w^\ell (1+w)^{-2\ell} v^\ell (1+v)^{-\ell} (z(1+w)^2+v(1+z)(z+w^2)... 2 Since$$\phi_S(x)=\sum_{i=0}a_ix^i=a_0+a_1x+a_2x^2+a_3x^3+\dotsb$$Therefore a_0=\phi_S(0)=1 and a_1=\phi_S'(0). So take the derivative and compute it at x=0 to get a_1. Similarly take second derivative to get a_2. 2 Hint. Considering S(x) = \sum_k a_k x^k we have$$ S(x) -x\frac{d}{dx}\left(x S(x)\right)+x^4\frac{d}{dx}\left(\frac{S(x)}{x}\right) = 0 $$and solving for S(x) we obtain$$ S(x) = C_0 (1-x)e^{-\frac 1x} $$1 Some general results that might be interesting. As the OP said, generating functions do seem like a good method for this kind of recurrences. Let's consider a more general homogeneous second order linear recurrence with coefficients linear in n:$$\left(A_2 n+B_2 \right) a_{n+2}+\left(A_1 n+B_1 \right) a_{n+1}+\left(A_0 n+B_0 \right) a_n =0$$Now let'... 1 Let's use linear algebra. If we take the matrix$$A = \begin{pmatrix}1 & 4 & 8 \\ 1 & 1 & 1\end{pmatrix}$$we want to solve$$Ax = \begin{pmatrix}X \\ Z\end{pmatrix}.$$Now if this system has a solution at all, then the set of all solutions is described by the kernel of A. This kernel has dimension one (over \mathbb{Q}, for example), so ... 1 Using the derivatives to fill in a Taylor series expansion...$$ f(a) + \frac{f'(a)}{1!}(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \cdots \\ \frac{x}{1! (1-s)} + \frac{x^3}{3! (3 - s)} + \frac{x^5}{5! (5 - s)} + \cdots \\ \sum_{n=1}^\infty \frac{x^{2n-1}}{(2n-1)!(2n-1-s)} $$This would be notoriously difficult to manually evaluate ot recognize as the expansion of a ... 1 I think what you need is the Euler's pentagonal theorem There is an interesting video about how Euler solved the problem of the partitions, linked the particular part but I recommend the entire video. Added: \prod_{i=1}^\infty (1-x^i) = \sum_{i=0}^\infty a_ix^i, a_i := \begin{cases}1 & \mbox{ if } i = \frac{1}{2}(3k^2 \pm k) \mbox{ and } k \mbox{ ... 1 Hint: Let$$f(x)=(1-x)(1-x^2)(1-x^3)(1-x^4)...(1-x^{1000})$$then the coefficient of x^n is \dfrac{f^{(n)}(0)}{n!} and for this purpose consider \ln f(x) and find a formula for n-th derivative. 1 How do you work out$$Q=(x^{a_1}+x^{a_2}+\cdots)(x^{b_1}+x^{b_2}+\cdots)\cdots(x^{r_1}+x^{r_2}+\cdots)?$$Well, you use the distributive law. You get the sum of a bunch of terms, each of which is a product of terms, taking one from each bracket. So it's a sum of terms of the form$$x^{a_{s_1}}x^{b_{s_2}}\cdots x^{r_{s_{\rm whatever}}}$$By the laws of ... 1$$\sum_{k=0}^0 k^3=0, \\\sum_{k=0}^1 k^3=1, \\\sum_{k=0}^2 k^3=9, \\\sum_{k=0}^3 k^3=36, \\\sum_{k=0}^4 k^3=100.  The requested formula must be a quartic polynomial, because the difference $P(n)-P(n-1)=n^3$ is a cubic polynomial. This polynomial is uniquely determined as the Lagrangian interpolation polynomial by the five above points. https://www....

1

There are several methods. There's the linear algebra method of finding difference formulas for $k^m$, treating a difference formula for a particular $m$ as a vector, then finding $\sum k^m$ in terms of those vectors. For instance, for $m=1$, we have $k^m-(k-1)^m = 1$. For $m=2$, we have $k^m-(k-1)^m = 2k-1$. If we call those $v_1$ and $v_2$ respectively, we ...

1

For a very thorough discussion, see e.g. Wilf's "generatingfunctionology". A more "combinatorial" view is given by Sedgewick and Flajolet "Analytic Combinatorics". Both are freely available, the second one is significantly heavier going (but you'd just want the more descriptive view there). Short answer: If the objects are interchangeable (not distinguished ...

1

We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects. Since here we have unlabelled (not marked e.g. with numbers) red, white and green balls we use ordinary generating functions and obtain \begin{align*} \color{blue}{[x^n]}&\color{blue}{\left(1+x+x^2+\...

Only top voted, non community-wiki answers of a minimum length are eligible