How can I prove the following recurrence relation for Laguerre polynomials. $$ (n+1)L_{n+1}(x)=(2n+1-x)L_n(x)-nL_{n-1}(x) $$ please help me. thanks
120872
Laguerre polynomials has the recurrence relation $$(n+1) L_{n+1} (x)=(2n+1-x) L_n (x)-nL_{n-1} (x)$$  In proving this, I differentiate the generating function of laguerre polynomials $$g(x,t)=\frac{e^{-\frac{xt}{1-t}}}{(1-t)}=\sum_{n=0}^\infty L_n (x)t^n $$  The process goes like this: \begin{align} \frac{\partial g}{\partial t} &amp;=\frac{(1-t) D_t \left(e^{-\frac{xt}{1-t}}\right)-e^{-\frac{xt}{1-t}} D_t \left(1-t\right) }{(1-t)^2}\\ &amp;=e^{-\frac{xt}{1-t}} \frac{1-t-x}{(1-t)^3} \end{align} $$(1-t)^2  \frac{\partial g}{\partial t}=(1-t-x)g  \tag 1$$  solving the right-hand side of eq. (1), we have: \begin{align} (1-t-x)g &amp;=(1-t-x) \sum_{n=0}^\infty L_n (x)t^n\\ &amp;=L_0 (x)-xL_0 (x)+\sum_{n=1}^\infty(L_n (x)-L_{n-1} (x)-xL_n (x) )  t^n \end{align}  also, Solving the left-hand side of eq. (1), we have: $$ \begin{align} (1-t)^2 \sum_{n=0}^\infty nL_n (x) t^{n-1}&amp;=(1-2t+t^2)\sum_{n=0}^\infty nL_n (x) t^{n-1}\\ &amp;=\sum_{n=0}^\infty nL_n (x)(t^{n-1}-2t^n+t^{n+1})\\ &amp;=L_1 (x)+\sum_{n=1}^\infty t^n [(n+1) L_{n+1}(x)-2nL_n (x)+(n-1)L_{n-1} (x) ].  \end{align} $$         My question is: How did the derivative of the generating function with respect to $t$ in the left hand side equal to $\sum_{n=0}^\infty nL_n (x) t^{n-1}$ that is, $$ \frac{\partial g}{\partial t}=\sum_{n=0}^\infty nL_n (x) t^{n-1} $$ Thanks! :)
121387
Is it true or false that $\lvert P([0, 1]) \setminus P((0, 1)) \rvert &gt; \lvert P(\mathbb{N}) \rvert$ ?  I need a hint because I don't see a way to solve this
39434
How do I find the lim for a series that has the following recurrence relation  $$ a_{0}=2 $$ $$a_1=16 $$ and $$a_{n+1}^2=a_na_{n-1} $$ .I applied $\ln$ and I substituted $$ b_n=\ln (a_n) $$ and so I found the following recurrence relation $$2b_{n+1}=b_n+b_{n-1}$$ .What do I do next? Can someone explain this limit in recurrence relation method because I'm not very familiar with it. I understood that it can only be applied if the given series converges?
64532
I have $P(x)$ a polynomial with degree $n$ ,$P(x) \ge 0$ for all $x \in$ real.  I have to prove that:     $f(x)=P(x)+P'(x)+P"(x)+......+P^{n}(x) \ge 0$ for all $x$.   I tried different methods to solve it but I got stuck.Any suggestion or advice is welcomed.
6935
Consider the following sequence :  $x_{0}=a$ , $x_{1}=b$ ,  $x_{n+1}=\bigl(1-\frac{1}{2n}\bigr)x_{n}+\frac{1}{2n}x_{n-1}.$ Find $\displaystyle \lim_{n\to \infty}x_{n}.$  I calculate $x_{2}$ , $x_{3}$ ,$x_{4}$ ,but I could not find any relationship  between any two consecutive pair. But I found that the sum of the coefficients of $a$ &amp; $b$ is equal to the term in denominator in each $x_{i}$.  How we find this limit...?
12559
Express recurrence relation  of the integral  $$ I_n=\int\frac{dx}{(1+x^2)^n} $$  [My Answer]  $$ I_n = \int\frac{1+x^2}{(1+x^2)^n}dx-\int\frac{x^2}{(1+x^2)^n}dx $$  $$ I_n=I_{n-1}-\int x\cdot\frac{x}{(1+x^2)^n}dx $$  $$ I_n=I_{n-1}-\frac{x}{2(1-n)(x^2+1)^{n-1}}+\frac{1}{2(1-n)}I_{n-1} $$  $$ I_n=\frac{2n-3}{2(n-1)}I_{n-1}+\frac{x}{2(n-1)(x^2+1)^{n-1}} \ \ \ \ (n&gt;1) $$  $$ I_1=\arctan(x) $$  Is my answer correct?
63208
This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n &gt; 1$,  where $u_0 = 0$ and $u_1 = 1$.   Show that     $$u_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$    Please help me with its proof. Thank you.
100703
Given a positive integer $n$, express$$ f_n(x) = \left|\begin{array}{c c c c c}  1 &amp; x &amp; \cdots &amp; x^{n - 1} &amp; x^n\\ x &amp; 1 &amp; x &amp; \cdots &amp; x^{n - 1} \\ \vdots &amp; x &amp; \ddots &amp; \ddots &amp; \vdots\\ x^{n - 1} &amp; \vdots &amp; \ddots &amp; 1 &amp; x\\ x^n &amp; x^{n - 1} &amp; \cdots &amp; x &amp; 1 \end{array}\right| $$   as a polynomial of $x$.   I tried to find a recurrence relation of $\{f_n\}_{n \geqslant 1}$ using Laplace expansion, but there seems to be no patterns in the minors in the expansion. Is there a somewhat simple recurrence relation of $\{f_n\}_{n \geqslant 1}$ or these determinants can be computed with other methods?
108367
Here's the problem:  1.Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three steps at the time.  2.Explain how the relation is obtained  3.What are the initial condition (base case)  4.How many ways can this person climb a flight of nine stairs  5.Show that this number is an exponential function of n. That is, find a real constant $c &gt; 1$ such that this number is at least $c^n$.  I know the recurrence formula is $C_n = C_{n-1} + C_{n-2} + C_{n-3}$, but for question five, I used induction to show $C_n &gt;= c^n$ for some constant c, but  $C_n &gt;= c^{n-1} + c^{n-2} + c^{n-3} &gt;= c^n * (1/c + 1/c^2 + 1/c^3)$  since $1/c + 1/c^2 + 1/c^3$ is a less than 1 for $c &gt; 1$, I don't know how $C_n$ is guaranteed $&gt;= c^n$  Thanks!
119842
Let $n$ be a positive integer, $x_0, x_1,\ldots,x_n$ be $(n+1)$ pairwise distinct real numbers, and $y_0, y_1,\ldots,y_n$ be $(n+1)$ real numbers. We have know that there exists a unique polynomial $P(x)$ where its degree is not greater than $n$.  What is the necessary and sufficient condition guaranteeing $P(x)$ has a degree of $n$.  Thank you for all comments and helping.
35622
I've been going through  and have a question on the inductive proof for the . Recurrent relation:  $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + 1$  Closed form hypothesis:  $J(2^m + l) = 2l + 1$, for $m \ge 0$ and $0\le l&lt;2^m$  Inductive Proof (for the even case):  $J(1)=1$ $J(2^m+l)= 2J(2^{m-1}+l/2)-1=2(2l/2+1)-1=2l+1$  How do the authors get from $2J(2^{m-1}+l/2)-1$ to $2(2l/2+1)-1$?
24080
How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients.  $a(n)-P\,a(n-1)-Q\,a(n-2)-R\,a(n-3)=0$  with the initial terms of a1, a2, and a3  and given that the roots of the characteristic equations have   two repeated roots and a real root three repeated roots   (can you give answers for both cases please)  For second order recurrence relations I know that you can use generating functions to deduce a closed form because it is then expressed as a arithmetic series which can be converted into a closed form.  However in the case of the general term of the third order recurrence relations if I follow the same steps what I did with the second order recurrence relation, instead of getting a simple arithmetic series I seemed to get a second order recurrence relation inside the series.  What am I doing wrong?  or is there a different method of approach in this case?  When I search the web I get these results  S(n) = nAx1^n + Bx1^n + Cx2^n,for the case when there are two repeated roots  and  S(n) = n^2Ax^n + nBx^n + Cx^n, for the case when there are three repeated roots  I just don't know how to get to these results  Please help
78087
I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated to be 2x1 tiles) and 2x2 tiles, if the 1x2 tiles come in 5 different colors and the 2x2 tiles in 4 different colors. Find and solve a recurrence relation for $t_n$.  I think I first part of 1x2 tiles to be : $t_n=3t_{n-1} +9t_{n-2}$  Is that part right? and how do i go from here
26155
I am working on  problem 3 from MIT's Fall 2010 OCW class 6.042J. This is covered in  which is about recurrences.  Here is the problem:  $$A_0 = 2$$ $$A_{n+1} = A_n/2 + 1/A_n, \forall n \ge 1$$  Prove   $$A_n \le \sqrt2 + 1/2^n,  \forall n \ge 0$$  I have graphed the recurrence and the upper bound and they seem to both converge on $\sqrt2$.    Also, if you ignore the boundary condition $A_0 = 2$ then you find that $\sqrt2$ is a solution to the main part of the recurrence. i.e. $\sqrt2 = \sqrt2/2 + 1/\sqrt2$.  The chapter and videos on recurrences have a lot to say about a kind of cookbook solution to divide and conquer recurrences which they call the Akra-Bazzi Theorem. But this recurrence does not seem to be in the right form for that theorem. If it were in the form $A_{n+1} = A_n/2 + g(n)$ then the theorem would give you an asymptotic bound. But $1/A_n$ is not a simple function of $n$ like a polynomial. Instead it is part of the recurrence.  Also, the chapter has a variety of things to say about how to guess the right solution and plug it into an inductive proof, but I haven't had much success. I have tried possible solutions of various forms like $a_n = \sqrt2+a/b^n$ and tried solving for the constants $a$ and $b$ but to no avail.  So, if someone can point me in the right direction that would be great. I always assume that the problem sets are based on something taught in the videos and in the text of the book but I am having trouble tracking this one down.  Bobby
92609
Usually, the Stirling numbers of the first kind are defined as the coefficients of the rising factorial: $(*) \prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$.   With this definition, a recursive relation of $S(n,i)$ be derived, and it can be shown that is coincides with the recursive relation on the number of permutation on an n-set with i cycles and they have the same initial conditions, hence they coincide.   1) Is there any possibility to do it the other way around, i.e., define $S(n,i)$ combinatorially and then to show that $\prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$ holds for $x \in \mathbb{N}$ by some combinatorial argument, and thus it is a polynomial identity?  (For Stirling numbers of the second kind, it is possible: it can be shown that $n^k = \sum_{i=0}^{k} \binom{n}{i} i! S_2(k,i)$ combinatorially ($n^k$ counts function from $[k]$ to $[n]$).)  2) Additionally: equating coefficients in $(*)$ shows that $S(n,i)$ is the elementary symmetric polynomial on $n$ variables of degree $n-i$ evaluated on $(0,1,\cdots ,n-1)$. Is there a combinatorial interpretation of this?
92828
Suppose $\left\{a_n\right\}_{n=0}^{\infty}$ is sequence . and we have below recursion relation$$\begin{cases}a_n=\sum_{k=0}^{n-1}a_ka_{n-k-1}\\\\a_0=1\end{cases}$$  If $f(x)=\sum_{n=0}^{\infty}a_nx^n$  is generating function of $a_n$ which one is correct .  $$1)\space f^2(x)+xf(x)-1=0\\ 2)\space f^2(x)-xf(x)+1=0 \\ 3)\space xf^2(x)+f(x)-1=0 \\ 4)\space xf^2(x)-f(x)+1=0 $$ I am sorry to ask this question , But as honestly as possible it was my student's question. I forgot this type of question . Can you help me or give me a clue . Thanks in advanced.
36996
$\int_{-1}^{1}(1-x^2)^ndx$  I have trouble with finding recurrence formula for this integral. $n$ is natural parameter. I've tried to split up $(1-x^2)^n = (1+x)^n(1-x)^n$ and then to integrate partially, but it only makes things more complicate.  Maybe substitution $x=sint$ can lead to solution? When I apply it I get:   $\int_{-\pi/2}^{\pi/2}(cost)^{n+1}dt$  What to do next then?