Problems

Solution: First notice that \(u_n = \alpha^n\) and \(u_n = \beta^n\) both satisfy the recurrence, since: \begin{align*} && a \alpha^2 + b \alpha + c &= 0 \\ \Rightarrow && a \alpha^{n+2} + b \alpha^{n+1} + c \alpha^n &= 0 \\ \Rightarrow && a u_{n+2} + bu_{n+1} + cu_n &=0 \end{align*} Notice also that if \(u_n\) and \(v_n\) both satisfy the recurrence, then any linear combination of them will satisfy the recurrence: \begin{align*} && \begin{cases} au_{n+2} + bu_{n+1} + cu_n &= 0 \\ av_{n+2} + bv_{n+1} + cv_n &= 0 \\ \end{cases} \\ \Rightarrow && a (\lambda u_{n+2}+ \mu v_{n+2}) + b (\lambda u_{n+1}+ \mu v_{n+1}) + c (\lambda u_{n}+ \mu v_{n}) &= 0 \end{align*} by adding a linear combination of the top two equations. Therefore it suffices to check that the constants \(A\) and \(B\) are such that we match \(u_0\) and \(u_1\). \(\frac{u_1 - \beta u_0}{\alpha - \beta} + \frac{u_1 - \alpha u_0}{\beta - \alpha} = u_0\) and \(\frac{u_1 - \beta u_0}{\alpha - \beta}\alpha + \frac{u_1 - \alpha u_0}{\beta - \alpha}\beta = u_1\). So we are done. Suppose we have another sequence, then we first notice that the first and second terms must be identical to each other. Suppose the first \(k\) terms are identical, then since the \(k+1\)th term depends only on the \(k\) and \(k-1\)th terms (both of which are equal) the \(k+1\)th term is the same. Therefore, by the principle of mathematical induction, all terms are the same. First notice that if you put \(v_n = (n+1)w_n\) we have \begin{align*} && 8(n+3)(n+2)(n+1)w_{n+2} - 2(n+3)(n+2)(n+1)w_{n+1} - (n+3)(n+2)(n+1)w_n &= 0 \\ \Rightarrow && 8w_{n+2}-2w_{n+1}-w_n &= 0 \end{align*} This has characteristic equation \(8\lambda^2 - 2\lambda - 1 = 0 \Rightarrow \lambda = \frac12, -\frac14\). Therefore the general solution is \(w_n = A \l \frac12 \r^n + B \l -\frac14\r^n\) and \(v_n = (n+1)\l A \l \frac12 \r^n + B \l -\frac14\r^n \r\). When \(n = 0\) we have \(A+B = 0 \Rightarrow B =-A\). When \(n=1\) we have \(1 = 2 \l \frac{A}{2} + \frac{A}{4} \r \Rightarrow A = \frac{4}{3}\), therefore \[ v_n = \frac{4}{3}(n+1) \l \frac{1}{2^n} + \l -\frac14\r^n \r\]

Solution: \(\displaystyle \int_x^{x+1} nP_{n-1}(x) \, dx = P_n(x+1) - P_n(x)\) Claim: \(P_{n}(x+1)-P_{n}(x)=nx^{n-1},\) for \(n \geq 1\) Proof: (By induction). (Base case, \(n=1\)). \(P_1(x) = x - \frac12\), \(P_1(x+1) - P_1(x) = 1 x^{0}\) as required. Assume the equation is true for \(n = k\). So \(P_k(x+1) - P_k(x) = kx^{k-1}\) now consider \begin{align*} P_{k+1}(x+1) - P_{k+1}(x) &= \int_0^{x+1} (k+1) P_k(t) \d t + P_{k+1}(0)- \int_0^{x} (k+1) P_k(t) \d t - P_{k+1}(0) \\ &= \int_0^x (k+1)(P_k(t+1)-P_k(t)) \d t + \int_0^1 (k+1)P_k(t) \d t \\ &= (k+1)x^{k} + 0 \end{align*} So by induction we are done. \begin{align*} n\sum_{m=0}^{k}m^{n-1} &= \sum_{m=0}^{k}n \cdot m^{n-1} \\ &= \sum_{m=0}^{k}\l P_n(m+1)-P_n(m) \r \\ &= P_n(k+1) - P_n(0) \end{align*} We need to find \(P_4\) \begin{align*} P_0(x) &= 1 \\ P_1(x) &= x - \frac12 \\ P_2(x) &= x^2 -x - \int_0^1 \l x^2 - x \r \d x \\ &= x^2 - x + \frac16 \\ P_3(x) &= x^3 -\frac{3}{2}x^2 + \frac12x - \int_0^1 \l x^3 -\frac{3}{2}x^2 + \frac12x \r \d x \\ &= x^3 -\frac{3}{2}x^2 + \frac12x \\ P_4(x) &= x^4 - 2x^3 + x^2 + c \end{align*} Therefore the sum we are interested in is \(\frac14 \l P_4(1001) - P_4(0) \r = \frac14 (1001)^2 (1001-1)^2 = (1001 \cdot 500)^2 = (500500)^2\)