Tag Info

Hot answers tagged

6

Divide everything by $(n!)^2$: $$\frac{f(n)}{(n!)^2} = \frac{n^2 f(n-1)}{(n!)^2} + n = \frac{f(n-1)}{((n-1)!)^2} + n.$$ If you write $g(n) = \frac{f(n)}{(n!)^2}$ you get $$g(n) = g(n-1) + n.$$ Since $g(1) = 1$, this becomes $g(n) = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ so that $$f(n) = (n!)^2 \frac{n(n+1)}{2}.$$


3

There is, I fear, not much to be done for lower values of $t$. But the asymptotics for $t\to\infty$ could reasonably be estimated, depending on the values of the parameters. For instance, if $b>0$, write $h(t)=tb^{-t}M(t)$ and consider the functional equation $$h(t+1)=\frac{t+1}th(t)+(t+1)b^{-t-1}\left(a+df(t)\right)+\frac cb \frac ...


2

I have an explicit solution, which I obtained by using the method of generating functions. First, compute what I called $P_n(1)$ from a recurrence relation. Then use those to compute explicit values of $M(k)$. $P_n(1)$ is the sum of the $M(k)$ values, for $0 \le k \le n$. You don't even need to compute all $P_n(1)$ values ahead of time. You can compute the ...


2

We have $a_n - a_{n-1} - 2n +2 = 0 \ (\star)$. Suppose the GF of $\langle a_n \rangle_{n\ge 1}$ is $f(x)$. Then, $$\begin{align*} f(x) &= a_1 + &a_2 x& + a_3 x^2 + \cdots + a_n x^n + \cdots \\ -xf(x) &= &-a_1 x& - a_2 x^2 - \cdots - a_{n-1}x^n - \cdots\\ \frac{-2x}{(1-x)^2} &= &-2 x& - 4 x^2 \ \ - \cdots - 2n x^n ...


2

To see any choice for the variables $q, p_1, p_2$ makes the desired relation hold, substitute the given form into the value of $a_n, a_{n-1}, a_{n-2}$ in your recurrence equation. Here, you must solve for $$\begin{align*}qn2^n+p_1n + p_2 & = 5(q(n-1)2^{n-1}+p_1(n-1) + p_2) \\ & - 6(q(n-2)2^{n-2}+p_1(n-2) + p_2) \\ & + 2^n + 3n\end{align*}$$ We ...


2

For an algebraic method, $$\binom{n-1}{a-1,b,c}+\binom{n-1}{a,b-1,c}+\binom{n-1}{a,b,c-1}$$ $$=\frac{(n-1)!}{(a-1)!b!c!}+\frac{(n-1)!}{(a)!(b-1)!c!}+\frac{(n-1)!}{a!b!(c-1)!}$$ $$=\frac{(n-1)!}{(a-1)!(b-1)!(c-1)!}\left(\frac{1}{bc}+\frac{1}{ac}+\frac{1}{ab}\right)$$ $$=\frac{(n-1)!}{(a-1)!(b-1)!(c-1)!}\left(\frac{abc(a+b+c)}{a^2b^2c^2}\right)$$ ...


2

I would separate the constant and $k$ terms like this: $\begin{array}\\ A(n) &=\sum_{k=0}^{n-1}\binom{n}{k}\frac{(-1)^{n-k}[2(n-k)-1]-1}{2}A(k)\\ &=\sum_{k=0}^{n-1}\binom{n}{k}(-1)^{n-k}(n-k)A(k)-\sum_{k=0}^{n-1}\binom{n}{k}\frac{(-1)^{n-k}+1}{2}A(k)\\ ...


1

A combinatorial argument is as follows. The number of ways we can put $n$ distinguishable balls into $3$ boxes of size $a,b,c$ respectively is $$\binom{n}{a,b,c}.$$ But, suppose we put $1$ ball into the box of size $a$ first. Now we can put $n-1$ balls into $3$ boxes of size $a-1,b,c$ respectively. This can be done in $\large\binom{n}{a-1,\ b,\ c}$ ways. ...


1

1) Use difference equations: $$ a_n = 3 a_{n-1} -a _{n-2} -1\\ \Delta a_{n+1} = a_{n+1} - a_n\\ \Delta a_{n+1} = 3 \Delta a_{n} - \Delta a_{n-1} $$ Now for simplicity set $b_n = \Delta a_n$ and use generating function and telescoping sums. 2) same


1

When characteristic polynomial has coincident roots the correct equation is the following: $$ f(n) = c_03^n + c_1 n\cdot 3^n $$ This phenomenon happens when you solve linear "things", like linear differential equations.


1

Yes, you’re doing something wrong. In the case of repeated roots, your approach collapses the two solutions into a single one, when in fact you need two independent solutions. If the characteristic equation has a root $r$ of multiplicity $m$, it gives rise to the $m$ solutions $c_1r^n,c_2nr^n, \ldots,c_mn^{m-1}r^n$. In your case $r=3$ and $m=2$, so you get ...


1

Let the roots of the characteristic equation be $\alpha, \beta$ so the equation is $$f(n)=(\alpha+\beta)f(n-1)-\alpha\beta f(n-2)$$ with solution $f(n)=A\alpha^n+B\beta^n$ We set $f(0)=3, f(1)=12$ to obtain $A+B=3$ and $A\alpha+B\beta=12$ with $B=\frac {3\alpha-12}{\alpha-\beta}$ and $A=\frac {12-3\beta}{\alpha-\beta}$ so $$f(n)=12\frac ...


1

The title mentions proving that $(a_n)$ is increasing, but you don't seem to handle that. More importantly, although you understand that the key to proving bounded-ness is $\sqrt{2+\sqrt2}<2$, you really need to work on the "style" of your induction proof. See for instance my answer here : Proof by Induction: By writing the induction steps in full ...


1

The is no relation between $T(m), T(n)$ for $m$ even and $n$ odd. For $m = 1, 2, \cdots$, we have $T(2m - 1) =T(1) + k(m - 1) , T(2m)=T(2)+k(m-1)$. Explicitly, for $K > \max\{T(1),T(2)/2,k/2\}$, we have $$T(x)<Kx$$, because $$T(x)=T(2m-1)=T(1)+k(m-1)<K+2K(m-1)=K(2m-1)=Kx$$ and $$T(x)=T(2m)=T(2)+k(m-1)<2K+2K(m-1)=K(2m)=Kx$$.


1

Actually, you need an initial value for $n=0$ and $n=1$, if you want to find the explicit formula for $T(n)$. Since you're asked to prove the solution is bounded, you may express the formula based on value of $T(0)$ and $T(1)$, and consider them as constants. Anyway, if I'm not making a mistake $T(n) = T(0) + \dfrac{n}{2}k$ if $n$ is even and $T(n) =T(1) + ...


1

Following Wikipedia's notation for the master theorem, you have $a=2,b=4,f(n)=16$. So $\log_b(a)=\log_4(2)=1/2$, so $f(n)=O(n^{\log_b(a)})$. So we are in case 1, and $T(n)=\Theta(n^{1/2})$. So somewhere you made a mistake.


1

How is the time till bankruptcy distributed? This is an application of the Hitting Time Theorem (see, e.g. here (Theorem 1) or pg. 79 of Grimmett and Stirzaker). $$P(\text{Ruined at game $n$ starting with $\$x$}) = \dfrac{x}{n}\binom{n}{(n-x)/2}p^{(n-x)/2}q^{(n+x)/2}.$$ Is the expected time till bankruptcy $= \infty$? Yes, if $p\geq q$. ...


1

$$a_{n+2}+4a_{n+1}-4a_n=2^n+7$$ $r-2=0$, $r=2$ $$a_n^{(\bar h)}=c_12^n+c_2n2^n$$ Guess: $\alpha2^n+\beta$ $$(\alpha2^n+\beta)+4(\alpha2^{n-1}+\beta)-4(\alpha2^{n-2}+\beta)$$ $$(\alpha2^n+\beta)+\alpha2^{n+1}+\underline{4\beta}-4\alpha2^{n-2}-\underline{4\beta}=2^n+7$$ $$\begin{align*} \alpha2^n+\alpha2^{n+1}-4\alpha2^{n-2}&=2^n\\ \beta&=7 ...


1

Your answer to the first question is correct. I’m guessing that in the second question you meant to write $$a(n)=5a(n-2)+a(n-3)+3a(n-4)+4\cdot5^{n-2}\;,$$ so that the non-homogeneous part is just $4\cdot5^{n-2}$. However, in that case the roots of the characteristic equation of the homogeneous part are not $5,3,3$, and $3$. If you did have a homogeneous ...


1

another observation is :$$a_n=a_{n-1}+2(n-1) ,\space \space \space a_1=2$$ $$\rightarrow a_n-a_{n-1}=2(n-1)\\$$ put $n=1,2,3,..(n-1)$ $$a_2-a_1=2(2-1 )=2(1)\\ a_3-a_2=2(3-1)=2(2)\\a_4-a_3=2(4-1)=2(3)\\...\\a_n-a_{n-1}=2(n-1)=2(n-1)\\$$no look at sum of them $$a_n-a_1=2(1)+2(2)+2(3)+...2(n-1)=\\2(1+2+3+4+...+(n-1))=2 \frac{(n-1)(n-1+1)}{2} ...


1

Direct Proof (my preferred way) The way I think about it is as a tree--it is a direct approach. It's hard to draw here, but I'll make my best effort: At the top of the tree, we have $n$ elements, which I'll just denote by $T_{n}$. When we apply the recursion, we get 2 children each with $T_{n/4}$ operations to perform (because of the coefficient in front ...


1

I don't think you need a recurrence relation to find the generating function: it's simply $$ \underbrace{(x+x^2+\dots+x^6)\dots(x+x^2+\dots+x^6)}_{4\text{ times}} = (x+x^2+\dots+x^6)^4.$$ Each $x^k$ term in the resulting expansion corresponds to one way to obtain $k$ from four dice.


1

We're given \begin{align*} a_n + b_n &= 2^n \tag{1}\\ a_n &= b_{n-1} \tag{2}\\ b_n &= 2a_{n-1} + b_{n-1} \tag{3} \end{align*} with initial conditions $a_1=0$, and $b_1=2$. By $(2)$, $a_2=b_1=2$, and now by $(1)$, $a_2+b_2=4\implies b_2=2$. From $(2)$, we get $a_{n-1} = b_{n-2}$, so we stick that into $(3)$ to get $b_n= 2b_{n-2} + b_{n-1}$. ...


1

I was staring at the problem last night and I got inspired. Using Pascal's Triangle, $$ \begin{matrix} 1 \\ 1 & 1\\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1\\ 1 & 5 & 10 & 10 & 5 & 1\\ \end{matrix} $$ Looking at column 2, for example we have $(3,9,18,30,...)$. Taking out a $3$ yields ...


1

In general such equations are called functional equations. In this case, assuming $A$ and $B$ are constants, for at least an open set of parameters $(\alpha, \beta)$ we can show that there is a solution of the ansatz form $$a(x) = \lambda \exp(\mu x)$$ just by substituting in the functional equation. Here, $\lambda$ can be prescribed freely and $\mu$ ...


1

Using the classical approach, start with the corresponding characteristic equation. If $$a_{k}=7a_{k-1}-10a_{k-2}$$ then $$r^2=7r-10$$ the roots of which being $2$ and $5$. So, the general form is $$a_k=c_1 2^k+c_2 5^k$$ Now, apply the conditions for $a_0$ and $a_1$; they will give you two linear equations with $c_1,c_2$ as unknwowns.


1

You can re-write your recurrence like $a_{n}-5a_{n-1}+7a_{n-2}-4a_{n-3}=0$ this gives rise (through a transformation that you'd see in any intro combinatorics text) to the polynomial that have $x^3-5x^2+7x-4=0$. There are three solutions (maybe some are complex) to that equation, say $r_1, r_2, r_3$. Then, the closed form expression for you sequence will ...


1

Is there a way of computing the $n$th number of a Lucas Sequence of the first kind (given parameters $P$ and $Q$) directly, without calculating each prior value in the sequence? Yes (assuming $P^2 \ne 4Q$), but it's unlikely to give any computational advantage: $$U_n(P,Q) = \frac{a^n - b^n}{a - b}$$ where $$a = \frac{P+\sqrt{P^2 - 4Q}}{2}\\ b = ...



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