# Tag Info

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 nth 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