Tag Info

New answers tagged

0

The "master theorem" by Leighton is applicable. For a recurrence $T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z))$ where $z \ge 0$, such that there are sufficient base cases; all $a_k > 0$ and $0 < b_k < 1$; there is a constant $c$ such that $\lvert g(z) \rvert = O(c^z)$; and all $\lvert h_k(z)\rvert = O(z /(\log z)^2$. Then for $p$ such ...


2

What you are doing is correct, except there was a typo where the '2' should be a '1'. $$ \begin{aligned} M(t)&=E(e^{tx})=\int_{-1}^{\infty} e^{tx} e^{-x-1} dx \\ &=e^{-1}\int_{-1}^{\infty} e^{(t-1)x} dx \\ &=e^{-1}\frac{1}{t-1}\left. e^{(t-1)x} \right|_{-1}^\infty \\ &=e^{-1}\frac{e^{1-t}}{1-t} \\ &=\frac{e^{-t}}{1-t} \\ \end{aligned} ...


0

In the "Update" (the day after the Question itself was posted), the OP mentions a recursion for counting the partitions of $n$ into $k$ distinct parts, each part at most $M$: $$ p_k(\leq M, \mathcal{D},n) = p_{k-1}(\leq M-1, \mathcal{D},n-k) + p_k(\leq M-1, \mathcal{D},n-k) $$ and asks "How can I prove this?". To see this, separate the ...


0

Perhaps easier than Michael Burr's method is to start with: $$ n a_{n + 1} = (n + 2) a_n $$ Define $A(z) = \sum_{n \ge 0} a_n z^n$, and remember: $\begin{align} \sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\ \sum_{n \ge 0} n a_n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} A(z) \end{align}$ Taking the recurrence, multiplying by $z^n$, ...


0

Easiest is to define: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ then shift indices so there aren't subtractions there: $$ a_{n + 2} = 4 a_{n + 1} - 4a_n + \binom{n + 2}{2} 2^{n + 2} + 1 $$ Multiply by $z^n$ and sum over $n \ge 0$: $$ \sum_{n \ge 0} a_{n + 2} z^n = 4 \sum_{n \ge 0} a_{n + 1} z^n - 4 \sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} \binom{n + ...


2

You can find a formula on Wikipedia: $\sum \limits _{n=1} ^\infty H_n ^{(m)} x^n = \frac {\mathrm{Li}_m (z)} {1-z}$, where $\mathrm{Li}_m$ is the polylogarithm. I doubt that you will be able to find something involving more elementary functions.


0

Cleaned up version of the question, with correct answer: Find the generating function for the sequence $\{1 / (n + 1)!\}$. The generating function is: $\begin{align} G(z) &= \sum_{n \ge 0} \frac{1}{(n + 1)!} z^n \\ &= \frac{1}{z} \sum_{n \ge 0} \frac{z^{n + 1}}{(n + 1)!} \\ &= \frac{1}{z} \left( \sum_{n \ge 0} \frac{z^n}{n!} - 1 ...


1

We have: $$ C_{k+1}-C_k = \frac{3k\, 4^k\, \Gamma\left(k+\frac{1}{2}\right)}{\sqrt{\pi}\,\Gamma(k+3)}\tag{1} $$ hence: $$ \sum_{k\geq n}\frac{C_{k+1}-C_k}{4^k} =\frac{(6n+2)\,\Gamma\left(n+\frac{1}{2}\right)}{\sqrt{\pi}\,\Gamma(n+2)} \tag{2}$$ and: $$\begin{eqnarray*} \sum_{n\geq 1}\frac{C_{n+1}-2C_n}{4^n}\sum_{k\geq n}\frac{C_{k+1}-C_k}{4^k} &=& ...


1

Assuming $p(n)=0$ for $n<0$, $$p(n) = \frac{1}{n!}\left.\frac{d^n}{dx^n}F(x)\right|_{x=0}.$$ If your $F(x)=Ae^{Bx}x^C$, for $C$ a positive integer, then: $$F(x)=A\sum_{n\geq 0} \frac{B^nx^{n+C}}{n!},$$ giving $$p(n)=A\frac{B^{n-C}}{(n-C)!},$$ for $n\geq C$ and $p(n)=0$ otherwise.


1

This is slightly reverse-engineered; I don't know whether I would have come up with it without knowing the answer – but it's certainly something that someone with much experience with such things could come up with. First, note that both values of $f$ are being multiplied by one more than their argument, so the right-hand side suggests considering ...


0

Note that $\Gamma(n+3)=(n+2)!$. $$f(n) = \frac{2\Gamma(n+3) - 5!(n+2)}{n+1}=\frac{2(n+2)! - 5 \cdot !(n+2)}{n+1}$$ Once one has this form, it is not hard using induction: \begin{align*} f(n+1)&=(n+1)f(n)+nf(n-1) \\ &=\frac{2(n+2)! - 5 \cdot !(n+2)}{n+1}(n-2)+\frac{2(n+1)! - 5 \cdot !(n+1)}{n}n \\ &= 2(n+2)! - 5 \cdot !(n+2) + 2(n+1)! - 5 \cdot ...


2

Note: This answer is a supplement to the beautiful answer of @Winther. It's in no way an alternative, but an additional examination. OPs question which is R.P. Stanleys problem $47c$ in Enumerative Combinatorics Ed.02 and his elaboration give rise to some questions and I was curious to find some information. We know from @Winther that due to the ...


2

You have $ (k+1) \binom n {k+1} = (k+1) \frac{n!}{(k+1)!(n-k-1)!} = \frac{n!}{k!(n-1-k)!} = n \frac{(n-1)!}{k!(n-1-k)!}= n \binom{n-1} k$. You then have $\sum_{k=0}^{49} (k+1) \binom{50}{k+1} x^k = \sum_{k=0}^{49} 50 \binom{49}{k} x^k = 50 \cdot (1+x)^{49}$, because $\sum_{k=0}^n \binom n k x^k= (x+1)^n$.


1

Yes, you can cancel. In general we have $\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}$. This can be verified in various ways. For example we can operate mechanically, expressing the binomial coefficients in terms of factorials. Thus $(k+1)\binom{50}{k+1}=(k+1)\cdot\frac{50}{k+1}\binom{49}{k}=50\binom{49}{k}$. Another way: Write down the binomial expansion of ...


13

There are infinitely many differentiable functions $F\colon [0,\infty)\to\mathbb{R}$ that satisfy $$ F'(x)=F(2x)\qquad\text{and}\qquad F(0)=1. $$ We will follow the argument outlined by @HenningMakholm in the comments. First, consider the substitution $G(x) = F\left(\dfrac{2^x}{\log 2}\right)$. Plugging this into the above equation gives $$ G\,'(x) = 2^x ...


1

There's no easy way, I'm afraid... My suggestion would be to write the well-known Taylor series expansions for both the exponential and error function, where that of the latter can be found by integrating the former term by term, and then employ the dreadful Cauchy product formula for their multiplication.


2

It might be better to consider the exponential generating function in this case. \begin{align} a_{n} &= \frac{n!}{(2n)!} \\ f(t) &= \sum_{n=0}^{\infty} a_{n} \, \frac{t^{n}}{n!} = \sum_{n=0}^{\infty} \frac{t^{n}}{(2n)!} = \cosh(\sqrt{t}). \end{align} Linear generating function: \begin{align} g(t) &= \sum_{n=0}^{\infty} a_{n} \, t^{n} \\ &= ...


1

$$g(x)=1+e^{x/4}\frac{\sqrt{\pi x}}{2} \mbox{erf}(\sqrt{x}/2).$$


6

I guess that you would like to express $a_n$ in terms of $b_n$. From $$ a_{n+1}d^{n+1}+nd^{n-1}a_n=b_n \tag1 $$you have, assuming $d \neq0$, $$ a_{n+1}+nd^{-2}a_n=d^{-n-1}b_n \tag2 $$ and you obtain $$ \frac{(-1)^n}{\prod_{k=1}^n(kd^{-2})}a_{n+1}-\frac{(-1)^{n-1}nd^{-2}}{\prod_{k=1}^n(kd^{-2})}a_n=\frac{(-1)^n}{\prod_{k=1}^n(kd^{-2})}d^{-n-1}b_n \tag3 $$ ...


0

Your "mountain" of coins is a special type of so-called "fountain" of coins. For an explicit answer to your question (spoiler alert: it involves Fibonacci numbers), see example 7 of chapter 2 in Wilf's generatingfunctionology. For a more general description of fountains of coins (where the rows aren't necessarily contiguous blocks), see his and Odlyzko's ...


0

From https://en.wikipedia.org/wiki/Perron%27s_formula : Let $a(n)$ be an arithmetic function, and let $$g(s)=\sum_{n=1}^{\infty} \frac{a(n)}{n^{s}}$$ be the corresponding Dirichlet series. Presume the Dirichlet series to be uniformly convergent for $\Re(s)>\sigma$. Then Perron's formula is $$ A(x) = {\sum_{n\le x}}' a(n) =\frac{1}{2\pi ...


0

I think I solved it. The Zeta function and it's equation for Bernoulli numbers is for $B_n(1)$, not $B_n(0)$. And the generating function for $B_t(x)$ is $\frac{t e^{x t}}{e^t-1}$. So it works.


7

The operator $e^{t(x+D)}$ is an exponential generating function for the sequence $(x+D)^n$. The commutator of the two operators $x$ and $D$ is given by $[x,D] = xD - Dx = -1$ and $[[x,D],x] = [[x,D],D] = 0$ so by Baker-Campbell-Hausdorff we have $$e^{(x+D)t}=e^{xt}e^{tD}e^{\frac{t^2}{2}}$$ or $$\sum_{n=0}^\infty \frac{(x+D)^nt^n}{n!} = \sum_{i=0}^\infty ...


19

Algebraically, what's happening is that taking an ordinary generating function is a bijection between the vector space of sequences and the ring of formal power series. In the ring of formal power series you have additional algebraic structure coming from the multiplication operation (and the division operation, when applicable). Operations like ...


2

Suppose I need to pick $5$ people from a group $19$ people conveniently numbered $1, \ldots, 19$. One method would be to first pick the $(i+1)$th person and the $(i+j+2)$th person. Then, I will select one of the $i$ people numbered $1, \ldots i$, and one of the $j$ people numbered $i+2, \ldots, i+j+1$, and one of the $k = 17-i-j$ people numbered ...


0

I think your calculation is correct. Observe that \begin{align*} B_{n,k}^{e^x}(0)=\frac{1}{k!}\sum_{j=0}^k\binom{k}{j}j^n(-1)^{k-j}=\left\{n \atop k\right\} \end{align*} yield the Stirling Numbers of the second kind.


6

The other answers are way too complicated for this particular problem. They're useful in more general cases, but they're completely overkill here. \begin{align*} K(n) &= 2 K(n - 1) - K(n - 2) + C \\ K(n) - K(n - 1) &= K(n - 1) - K(n - 2) + C \end{align*} Just look at this equation for a few seconds. It's literally telling you that the difference ...


2

More standard way. Rewrite your equation: $$ K(n)-2K(n-1)+K(n-2)=C \tag{1}\label{1} $$ Solution of this is $K=K_0+K_{part}$, where $$ K_0(n)-2K_0(n-1)+K_0(n-2)=0\tag{2}\label{2} $$ and $K_{part}$ is any solution of $\eqref{1}$. Now we're finding solution of homogenuous equation $\eqref{2}$ in a form $K(n)=\mathrm{const}\cdot \lambda^n$ and get ...


9

$$ \begin{bmatrix} K(n+1) \\ K(n) \end{bmatrix}=A \begin{bmatrix} K(n) \\ K(n-1) \end{bmatrix}+ \begin{bmatrix} C \\ 0 \end{bmatrix} $$ where $$A= \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix} $$ So, $$ \begin{bmatrix} K(n+1) \\ K(n) \end{bmatrix}=A^n \begin{bmatrix} K(1) \\ K(0) \end{bmatrix}+ \left(\sum_{k=1}^{n-1}A^k+I\right) \begin{bmatrix} C ...


5

To keep things general, suppose $k_0=A$ and $k_1=B$. Then the next few terms are: $$k_2=2A-B+C\\ k_3=4A-3B+3C\\ k_4=6A-5B+6C\\ k_5=8A-7B+10C\\ k_6=10A-9B+15C$$ The pattern seems to be (for $n\ge2$) that 2 more $A$'s are added, 2 more $B$'s are subtracted, and $n-1$ more $C$'s are added, $$k_n=(2n-2)A-(2n-3)B+\frac{(n-1)(n)}{2}C$$ A proof by strong ...


1

If you change you generating function you can have easier generating functions for a very similar sequence. By example, if you had $F_n(x)=\sum_{k\ge 0}\binom{n}{2k}x^{2k}$ instead of just $x^k$ then you can see that $$F_n(x)=\frac{g(x)+g(-x)}{2},\quad g(x)=\sum_{k\ge 0}\binom{n}{k}x^k=(1+x)^n\\ ...


0

You can express your close-to-geometric sum as the difference between sums, i.e. $$f(x)=\sum_{k\ge 0} x^k -x^3=\frac{1}{1-x}-x^3=\frac{1-x^3+x^4}{1-x}$$ Then we have $$F(x)=\left(\frac{1-x^3+x^4}{1-x}\right)^5=\sum_{j\ge0}\binom{j+4}{4}x^j\cdot\sum_{a+b+c=5}\binom{5}{a,b,c}(-1)^bx^{3b+4c}$$ and equating coefficients we have that $10=j+3b+4c\ \to ...


1

Yes, the binomial expansion of $(1-x)^{-4}$ will work. No, many other type of questions like this can not be solved by this method. Here is a useful expansion: $(1-x)^{-n} =\sum_{k=0}^{\infty} \binom{-n}{k}(-x)^k =\sum_{k=0}^{\infty} (-1)^k\binom{-n}{k}x^k $. And, $\begin{array}\\ \binom{-n}{k} &=\frac{(-n)(-n-1)(-n-2)...(-n-k+1)}{k!}\\ ...


3

I will assume you are asking for how many solutions with $x_i\in\mathbb{N}$ for each $i$ (where $\mathbb{N}=\{0,1,2,\dots\}$). If you are looking for real solutions, there are clearly infinitely many. The number of integral solutions to $x_1+x_2+\dots+x_k=n$ with each $x_i\geq 0$ is given as $$\binom{n+k-1}{k-1}$$ This can be seen via stars&bars.


1

Since $2s^2+3s-9=(s+3)(2s-3)$, we have: $$\frac{4s^2}{9-3s-2s^2}=-2+\frac{4}{s+3}-\frac{1}{s-3/2}\tag{1}$$ and now we just need to exploit: $$\forall \alpha:|\alpha|<1,\qquad \frac{1}{1-\alpha s} = \sum_{n\geq 0} \alpha^n s^n. \tag{2}$$


2

Consider $t_{n+1} = (1+c~q^{n})~p~t_{n} + a + b + (n+1)bq$ for which \begin{align} \sum_{n=0}^{\infty} t_{n+1} \, x^{n} &= p \, T(x) + c \, p \, T(q x) + \frac{a + b}{1-x} + b q \, \partial_{x} \left( \sum_{n=0}^{\infty} x^{n} \right) \\ \frac{T(x) - t_{0}}{x} &= p \, T(x) + c \, p \, T(q x) + \frac{a + b}{1-x} + b q \, \partial_{x} \frac{1}{1-x} ...


2

robjohn already has a solid answer for you, but here's another approach if you're more inclined to conditioning, which I see you considered in the comments. Let $Q_{1}$ be the waiting time for the first "$S$". Then, as you noted, $Q_{1} \sim Geo(\frac{2}{3})$. Now we condition on the $(Q_{1}+1)$-th trial. We have that \begin{equation*} Q= ...


2

The atomic monomials are $ \begin{array}{} S=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^{\color{#C00000}{1}}&\text{length $\color{#C00000}{1}$, probability $\color{#00A000}{\frac23}$}\\ NS=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^\color{#C00000}{2}&\text{length $\color{#C00000}{2}$, probability ...


1

You can also use Inclusion–exclusion principle. Without the restriction $x_i\neq 3$ you have $$\binom{10+5-1}{10}$$ solutions. Now you need to check how many bad cases you have. Denote the set of all solutions with $x_i=3$ by $A_i$. Your bad cases are $$A_1\cup A_2\cup A_3\cup A_4\cup A_5.$$ Can you take it from here?


0

Note that $$ \frac{1-x^3}{1-x} = 1+x+x^2 $$ so in $(1+x+x^2)^5$ you are counting only the solutions with $0 \le x_i \le 2$ of which there is in fact only one. Note that $$ (1-x)\sum_{i\ne 3} x^i = \sum_{i\ne 3} x^i - \sum_{i\ne 0,4} x^i = 1 + x^4 - x^3 $$ So we are left with $$ \left(\frac{1 - x^3 + x^4}{1-x}\right)^5 $$ Now do your expansion again. ...


2

Case (b): Since we are looking for ordered representations of $n$ as a sum of $k$ distinct integers chosen from $T$, each element $t\in T$ can occur at most once. To select an element $t\in T$ exactly zero or one times is encoded with $$x^{0\cdot t}+x^{1\cdot t}=1+x^t$$ We observe: The product $$\prod_{t\in T}(1+x^t)=\sum_{n\geq ...


0

Note: This answer is a supplement to the comment of @1999. Let $(a_n)_{n\geq 0}$ denote a sequence of numbers. We can encode this information using different kinds of generating functions. Two customary variants are ordinary generating functions: $\sum_{n=0}^{\infty}a_nx^n$ exponential generating functions: $\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}$ ...



Top 50 recent answers are included