New answers tagged

3

This is a homogeneous linear recurrence relation with constant coefficients. From $$ a_n = 10 a_{n-1} -21 a_{n-2} $$ you can infer the order $d=2$ and the characteristic polynomial: $$ p(t) = t^2 - 10 t + 21 $$ Calculating the roots: $$ 0 = p(t) = (t - 5)^2 - 25 + 21 \iff t = 5 \pm 2 $$ this gives the general solution $$ a_n = k_1 3^n + k_2 7^n $$ The two ...


11

The way to do this without generating functions is to start with the ansatz that $$ a_n = x^n $$ satisfies the recursion but possibly not the starting points at $n=0$ and $1$. If we have that solution then any $a_nkx^n$ satisfies the recursion as well. And if we have two such solutions $x^n$ and $y^n$ then any linear combination $a_n=kx^n+my^n$ will ...


5

This is called a linear homogeneous recurrence relation. If we look at the recursive case, we find that the coefficient of $a_{n-1}$ is $10$ and the coefficient of $a_{n-2}$ is $-21$. This means the "characteristic polynomial," which is basically the polynomial which tells us what the bases of the explicit formula will be, is like this: $$x^2-10x+21$$ Notice ...


0

To balance the gender-coded problem statement, I'll be distributing the cars to the girls and the dolls to the boys. So one car to each girl and one doll to each boy is clear, and we have $5$ cars and $5$ dolls left. Choose $k$ girls in $\binom5k$ ways and give at least one extra car to each of them and none to the others, in $\binom{5-1}{k-1}$ ways. Now ...


1

The product is \begin{align} &\frac{2-4t+2t^2-t^2x^2-t^2 x^3}{2t^2 x^2(1-t)^2}\exp\left(-\frac{tx}{1-t}\right)+\frac{tx+t-1}{t^2 x^2(1-t)}\\ ={}& \frac{2-4t+2t^2-t^2x^2-t^2 x^3}{2t^2 x^2(1-t)}\sum_{n\ge0}L_n(x)t^n+\frac{tx+t-1}{t^2 x^2(1-t)} \\ ={}& \frac1{2t^2x^2(1-t)}\left( \left(2-4t+2t^2-t^2x^2-t^2 x^3\right)\sum_{n\ge0}L_n(x)t^n+2(tx+t-1)\...


4

Now because the sequence grows so quickly, it is easy to see that only the terms containing $a_m$ in the sum are going to be significant. Thus $a_{m+1} \approx (4m + 1) (a_m a_1 + a_1 a_m) \approx 8m a_m$. This tell us that $a_{m+1} \approx 8^m m!$. This initial guess can now be improved. It is possible to prove by induction that there exists constants $\...


1

If we assume that $a_0=0$ and define $f(x)$ as: $$ f(x)=\sum_{n\geq 0} a_n x^{4n} \tag{1}$$ we have: $$ f(x)^2 = \sum_{n\geq 0}\left(\sum_{k=0}^{n} a_k a_{n-k}\right) x^{4n}\tag{2} $$ as well as: $$ x^4\cdot\frac{d}{dx}\left(\frac{f(x)^2}{x^3}\right) = \sum_{n\geq 0}(4n-3)\left(\sum_{k=0}^{n}a_k a_{n-k}\right)x^{4n} \tag{3}$$ and the recurrence relation ...


0

We can factor the expression for $T$ as follows: $T(x) = \sum_{k,r} r V_r V_{k-1} x^k = \left( \sum_k V_{k-1} x^k \right) \left( \sum_r r V_r \right).$ For the first factor, we have $\sum_k V_{k-1} x^k = x \sum_k V_{k-1} x^{k-1} = xU(x)$ (I presume this sum is over $k \ge 1$). Now, as you've noted, $\sum_r r V_r x^r = x U'(x)$. However, in the above ...


1

Suppose the generating function is $f(x)$. Then you have $$f(x)=1-x+x^2-x^3+\dots$$ Hence $$xf(x)=x-x^2+x^3-\dots$$ Adding these two we get $f(x)+xf(x)=1$, so $$f(x)=\frac{1}{1+x}$$


1

The main point is to write a recurrence for the sequence $a_n$: $$ a_{n+1}=-a_n, \qquad a_0=1 $$ The shift from $n$ to $n+1$ is reflected in $A(x)$ as multiplication by $x$. Therefore, if $A(x)= \sum a_n x^n$, then $xA(x)=1-A(x)$. Now solve for $A(x)$.


0

This sort of calculation can be substantially facilitated using generating functions. The probability generating function for the $i$-th contract is $1-p_i+p_ix$, where $p_i$ is the probability to win the contract and the coefficient of $x^k$ is the probability to win $k$ contracts. Then the probability generating function for all contracts together is the ...


0

These calculations are time consuming. I give you an examplary calculation. Let´s calculate the probability of winning 7 contracts. We have 8 different situations. Not winning contract 1 but winning the other contracts The probability is $(1-0.7)\cdot 0.45 \cdot 0.3\cdot 0.5 \cdot 0.55 \cdot 0.61\cdot 0.02\cdot 0.02$ Not winning contract 2 but ...


0

Like others have pointed out, the graph of both is not the same. There is a nontrivial singularity for the first function that is not present for the second. A simpler version of your question seems to be: Are the functions $f(x)=x$ and $f(x) = \frac{x^2}{x}$ the same? The answer is, yes, except at the point $x=0.$ They are different because by ...


1

They aren't quite the same function. They're the same function on all values where both are defined. The domain of the first is $\mathbb{R}\setminus \{0, -\frac{1}{2}, \frac{1}{3}\}$. The domain of the second is $\mathbb{R}\setminus \{-\frac{1}{2}, \frac{1}{3}\}$. Those aren't the same domain, so the two functions aren't the same. For any value in both ...


-1

let $$g(x)=\frac{x^2}{(1+2x)(1-3x)}$$ and $$f(x) = \frac{1} {(\frac1x+2)(\frac1x-3)}$$ we have $D_f=R-\{0,\frac{1}{3},\frac{-1}{2}\}$ and $D_g=R-\{\frac{1}{3},\frac{-1}{2}\}$, thus $g\ne f$


5

Since $$ \frac{1}{1-x^7} = \sum_{k\geq 0} x^{7k} \tag{1}$$ we have: $$ \frac{1+x+x^2}{1-x^7} = \sum_{n\geq 0} \eta(n)\, x^n \tag{2} $$ where $\eta(n)$ equals $1$ if $n\pmod{7}\in\{0,1,2\}$ and $0$ otherwise.


3

The generating function for this sequence is $f(x)=\prod\limits_{n=1}^{\infty} \cfrac{1}{1-x^{2n-1}}$ because $f(x)=(1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)\cdots (1+x^{2n-1}+x^{(2n-1)+(2n-1)})\cdots = (1+x+x^2+\cdots)(1+x^3+x^{2\cdot3}+\cdots)\cdots (1+x^{2n-1}+x^{2(2n-1)})\cdots=\cfrac{1}{1-x}\cfrac{1}{1-x^3}\cdots\cfrac{1}{1-x^{2n-1}}\dots=\prod\...


2

$$G_Y(t) = E(t^Y) = E(t^{\sum_{i=1}^NX_i}) = E(t^{X_1} \cdots t^{X_N}) $$ Now use conditional expectation on $N$ and independence of $X_i$ to find that $$ G_Y(t)= E(E(t^{X_1} \cdots t^{X_N} \mid N=n)) = E\left(\left(\frac{t+1}2\right)^N\right) = \frac{t+1}{2(2 - \frac{t+1}2)} = \frac{1+t}{3-t}$$


1

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \...


1

Another approach to this problem uses Poor man's Lagrange Inversion, which is the Cauchy Residue Theorem. We have $$(27x-4)T(x)^3+3T(x)+1 = 0$$ We thus obtain $$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$ Solve for $z$ to get $$z = \frac{4T(z)^3-3T(z)-1}{27 T(z)^3}.$$ Therefore the substitution $w=T(z)$ yields $$...


2

By the Lagrange inversion theorem, the solution of $w^3-w=-x$ has the following Taylor series: $$ w(x)=\sum_{k\geq 0}\binom{3k}{k}\frac{x^{2k+1}}{2k+1} $$ whose radius of convergence is $\frac{2}{3\sqrt{3}}$. If we set $y(x)=\sqrt{\frac{3}{4-27 x}}\,w(x)$, by Lagrange inversion: $$ y(x)=\sum_{k\geq 0}\binom{3k}{k}\frac{3(-1)^k}{(2k+1)(4-27x)^{k+1}}\tag{1}...


1

Each partition can be uniquely identified by how many copies of each number it uses. Hence, we get the generating function: $$\left(1+x+x^2+\dots\right)\left(1+x^3+x^6+\dots\right)\cdots\left(1+x^9+x^{18}+\dots\right)=\frac{1}{\left(1-x\right)\left(1-x^3\right)\cdots\left(1-x^9\right)}$$


0

Here is how I would go about it. It doesn't need recursion relations. First, define $$F(x)\equiv x^1+x^3+x^5+x^7+x^9$$ The coefficient of $x^n$ in $F(x)$ says how many ways there are of making $n$ out of one odd number less than $10$. The coefficient of $x^n$ in $F(x)^2$ says how many ways there are of making $n$ out of two odd numbers. For instance, for $...


0

Hint: $f(n)=f(n-9)+g(n)$, where $g(n)$ is the number of ways using only 1,3,5,7. $g(n)=g(n-7)+h(n)$ and so on.


1

Your $f(n)$ is the coefficient of $x^n$ (I will use the Wilf's notation $[x^n]$) in the product: $$ g(x)=\prod_{k=0}^{4}\sum_{n\geq 0}x^{(2k+1)n} = \prod_{k=0}^{4}\frac{1}{1-x^{2k+1}}\tag{1}$$ $g(x)$ is a meromorphic function with a pole of order $5$ at $x=1$, a pole of order $2$ at $x=\omega$ etc. You may use the residue theorem to find a partial fraction ...


0

We can find the result by nearly reverting the way $c_k$, the series with binomial coefficients was obtained. We use the coefficient of operator $[x^i]$ to denote the coefficient of $x^i$ in a series. This way we can write e.g. \begin{align*} [x^i](1+x)^n=\binom{n}{i} \end{align*} We obtain \begin{align*} c_k&=\sum_{i=0}^ka_ib_{k-i}\\ &=\...


0

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \...


0

I will state the identity as follows: $$ \sum_{i+j = n} (-1)^i \binom{r}{i} \binom{r+j}{r} = 1.$$ For any subset $A$ of $\{ 1,2, ... , r \}$, let $S_A$ be the set of solutions to the inequality $x_1 + ... + x_r \le n$ with $x_i$ non negative integers (for any $i$) and $x_i$ is positive for any $i \in A$. By the principal of inclusion exclusion, we have $$...


0

Your expression $g(x) = x^6 (1+x^2+\cdots+x^8)^3$ is correct, but the geometric series formula needs to be used correctly. Recall the geometric series formula for the sum of 5 terms: $a+ar+\cdots+ar^4 = \frac{a(1-r^5)}{1-r}$. In our case, $r=x^2$ and $a=1$. So $1+x^2+\cdots+x^8$ simplifies to $\frac{1-(x^2)^5}{1-x^2} = \frac{ 1-x^{10}}{1-x^2}$. Hence, ...


0

Here is variation of the theme which might be helpful when doing the calculation. It's convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. We obtain \begin{align*} [x^{24}]&(x^2+x^4+x^6+x^8+x^{10})^3\tag{1}\\ &=[x^{24}]x^6(1+x^2+x^4+x^6+x^8)^3\\ &=[x^{18}]\left(\frac{1-x^{10}}{1-x^2}\right)^...


5

When computing $1+x^2+(x^2)^2+(x^2)^3+(x^2)^4$, the series is in powers of $x^2$ not $x$. So the proper expression is $$1+x^2+(x^2)^2+(x^2)^3+(x^2)^4=\frac{1-(x^2)^5}{1-(x^2)}=\frac{1-x^{10}}{1-x^2}.$$ By contrast, $$\frac{1-x^{9}}{1-x}=1+x^1+x^2+\cdots +x^8$$ which differs from the above series in it has both odd and even powers of $x$.


0

Disclaimer: this is an elementary solution, I've never took discrete mathematics course. This gives recurrence of only 2nd order, but more complex and with square root, so maybe of less practical use. Let's denote $$ x= n, \ y= 3^n. $$ Write formulas for $f(n)$, $f(n+1)$, $f(n+2)$ using $x$ and $y$: \begin{align} f(n)\phantom{+} &= 2x + xy\\ f(n+1) &...


0

Disclaimer: this is an elementary solution, I've never took discrete mathematics course. I got recurrence of only 3rd order, but it seems all right. However, it's possible this is not the method you're supposed to use. Let's denote $$ x= 2n, \ y= 3^n n,\ z= 3^{n+1}. $$ (Those are linearly independent sequences of $n$, so we can't have fewer variables for ...


1

Let $X = \{ (u_0,u_1,u_2,\ldots) : u_i \in \mathbb{C} \}$ be the space of sequences indexed by $\mathbb{N}$, taking value in $\mathbb{C}$. It is a vector space with respect to componentwise addition and multiplication. Define a linear map $L : X \to X$ which shifts a sequence to the left. $$X \ni u = (u_0, u_1, \ldots ) \quad\mapsto\quad Lu = (u_1, u_2,\...


3

Nice problem, thank you. First, find the ordinary generating function for the sequence $f(n).$ We have $$ \sum_{n >0}f(n)z^n=\sum_{n >0}(2\,n +n\, 3^n)z^n=2\sum_{n >0}n z^n+\sum_{n >0}n 3^n z^n=\\=2\,{\frac {z}{ \left( z-1 \right) ^{2}}}+3\,{\frac {z}{ \left( 3\,z-1 \right) ^{2}}}={\frac {z \left( 21\,{z}^{2}-18\,z+5 \right) }{ \left( 3\,z-...


0

HINT: For a positive integer $k$ the polynomial $1+x^k$ is the generating function for the sequence whose $n$-th term is the number of ways of writing $n$ as a sum of distinct elements of the set $\{k\}$. If your product lemma is what I think it is, it says that if $k$ and $\ell$ are distinct positive integers, then the product $(1+x^k)(1+x^\ell)$ is the ...


2

Part (a) and (c) follow the form: $$f_{n} - a f_{n-1} = b \, c^{n}.$$ Since the generating function method is being asked then that is what will be demonstrated next. \begin{align} \sum_{n=0}^{\infty} \left( f_{n+1} - a f_{n} \right) t^{n} &= \frac{b}{1-c t} \\ \sum_{n=1}^{\infty} f_{n} t^{n-1} - a F(t) &= \\ \frac{1}{t} \, \left( F(t) - f_{0} \...


3

$$ \frac{1+\xi}{3-\xi}=\frac13\frac{1+\xi}{1-\frac\xi3}=\frac13(1+\xi)\sum_{k=0}^\infty\left(\frac\xi3\right)^k\;. $$


1

Here are a few thoughts on the problem, too long for a comment, but which do not constitute a satisfactory answer. First, as a consequence of the Weierstrass factorization theorem, given any countable collection $\{ z_j \} \subset \mathbb{D} = \{ \lvert z \rvert < 1 \}$ that has no accumulation point in the interior $\mathbb{D}$ and $\{ n_j \} \subset \...


1

For $n\gt 1$ we have $$\begin{cases}f(2n)=f(n)+f(n+1)\\f(2(n+1)+1)=f(n)+f(n+1)\end{cases}\Rightarrow \boxed {f(2n)=f(2n+3)}$$ It follows $$G(x)=(1+x+2x^2+2x^3+3x^5)+\sum_{n\gt 1}a_{2n}(x^{2n}+x^{2n+3})$$ where I have calculated the coefficients $2,3$ of $x^3,x^5$ respectively. We need the coefficients $a_4,a_6,a_8,...,a_{2n},…$ for which it holds the ...



Top 50 recent answers are included