Problems

---

Solution:

1. \begin{align*} && \sum_{i=0}^{\infty} x^{2i+1}&= \frac{x}{1-x^2} \\ \Rightarrow &&&=\frac12 \left ( \frac{1}{1-x} - \frac{1}{1+x} \right) \\ \underbrace{\Rightarrow}_{\int} && \sum_{i=0}^{\infty} \frac{1}{2i+1} x^{2i+2} &= \frac12 \left ( -\ln (1-x) - \ln(1+x) \right) \\ \underbrace{\Rightarrow}_{x = 1/2} && \sum_{i=0}^\infty \frac{1}{2i+1} \left (\frac12 \right)^{2i+2} &= -\frac12 \ln \frac12 - \frac12 \ln \frac32 \\ &&&= -\frac12 \ln \frac34 \\ &&\frac14\sum_{i=0}^\infty \frac{1}{2i+1} \left (\frac12 \right)^{2i}&= \frac12 \ln \frac43 \\ \Rightarrow&& S &= 2 \ln \frac43 \end{align*}
2. \begin{align*} \sum_{k=0}^{\infty} \left (2x^{4k} - x^{4k+1} - x^{4k+3} \right) &= \sum_{k=0}^{\infty} \left (2 - x^{1} - x^{3} \right) x^{4k} \\ &= \frac{2-x-x^3}{1-x^4} \\ &= \frac{(1-x)(2+x+x^2)}{(1-x)(1+x+x^2+x^3)} \\ &= \frac{2+x+x^2}{1+x+x^2+x^3} \end{align*}
3. \begin{align*} && \frac{1}{(1-x)^2} &= \sum_{r=0}^{\infty} r x^{r-1} \\ \Rightarrow && 9 &= \sum_{r=1}^{\infty} r \left ( \frac23 \right)^{r-1} \\ \Rightarrow && \sum_{r=2}^{\infty} r \left ( \frac{2^{r-2}}{3^{r-1}} \right) &= \frac12 \left ( 9 - 1 \right) \\ &&&= 4 \end{align*}
4. \begin{align*} && \frac{2}{r(r^2-1)} &= \frac{1}{r-1} - \frac{2}{r} + \frac{1}{r+1} \\ \Rightarrow && \sum_{r=2}^{\infty} \left ( \frac{1}{r-1} - \frac{2}{r} + \frac{1}{r+1} \right) &= \sum_{r=2}^{\infty} \left ( \frac{1}{r-1} - \frac{1}{r} - \frac{1}{r} + \frac{1}{r+1} \right) \\ &&&= \sum_{r=2}^{\infty} \left ( \frac{1}{r-1} - \frac{1}{r} \right)-\sum_{r=2}^{\infty} \left ( \frac{1}{r} - \frac{1}{r+1} \right) \\ &&&= 1 - \frac12 \\ &&&= \frac12 \end{align*}

---

Solution: Since the common difference is \(a_2 - a_1\) we can find that \(a_n = a_1 + (n-1)(a_2-a_1)\), then \begin{align*} && a_1 &&+&& a_2 &&+&& \cdots &&+&& (a_1 + (n-2)(a_2 - a_1) && + && (a_1 + (n-1) (a_2 - a_1)) \\ + && (a_1 + (n-1) (a_2 - a_1))&&+&& (a_1 + (n-2)(a_2 - a_1)&&+&& \cdots &&+&& a_2 && + && a_1 \\ \hline \\ = && 2a_1 + (n-1)(a_2 - a_1) && + && 2a_1 + (n-1)(a_2 - a_1) && + && \cdots && + 2a_1 + (n-1)(a_2 - a_1) && + 2a_1 + (n-1)(a_2 - a_1) \\ = && n(2a_1 + (n-1) (a_2 - a_1)) \end{align*} Therefore the sum is \(a_1 n + \frac{n(n-1)}{2} (a_2 - a_1)\). Since \(b_n - b_1 = (b_n - b_{n-1}) + (b_{n-1} - b_{n-2}) + \cdots (b_2 - b_1)\), \(b_n - b_1 = a_1 (n-1) + \frac{(n-1)(n-2)}{2}(a_2 - a_1) = (b_2-b_1)(n-1) + \frac{(n-1)(n-2)}{2}(b_3 -2b_2 +b_1)\). So \(b_n = b_1 + (b_2 - b_1)(n-1) + \frac{(n-1)(n-2)}{2} (b_3 - 2b_2 + b_1)\). In particular \begin{align*} \sum_{i=1}^n b_i &= \sum_{i=1}^n \l b_1 + (b_2 - b_1)(n-1) + \frac{(n-1)(n-2)}{2} (b_3 - 2b_2 + b_1)\r \\ &= nb_1 + (b_2-b_1) \frac{n(n-1)}{2} + \frac{n(n-1)(n-2)}{6}(b_3-2b_2+b_1) \end{align*} Let \(b_2 - b_1 = x\) and \(b_3 - 2b_2+b_1 = y\), then \begin{align*} b_4 - b_2 &= d &= &2x + 3y \\ b_6-b_4 &= 2d &=& 2x +(10-3)y \\ &&=&2x + 7y \\ 220-b_6&=6d &=& 220-(1 + 5x + 10y) \\ \end{align*} \begin{align*} && 4x + 6y &= 2x + 7y \\ && 6x+21y &= 219-5x-10y \\ \Rightarrow && 2x - y &= 0 \\ && 11x + 31y &= 219 \\ \Rightarrow && x &= 3 \\ && y &= 6 \end{align*} Therefore the final sum is \begin{align*} n + 3 \frac{n(n-1)}{2} + 6 \frac{n(n-1)(n-2)}{6} &= n^3-\frac32n^2+\frac32n \end{align*}

---

Solution: Integrating by parts we obtain: \begin{align*} \int x \ln x \, \d x &= [\frac12 x^2 \ln x] - \int \frac12x^2 \cdot \frac1x \d x \\ &= \frac12 x^2 \ln x - \frac14 x^2 + C \end{align*}

We should have: \begin{align*} \int_0^1 x \ln \frac{1}{x} \d x &= \lim_{n \to \infty} \sum_{i=1}^n \frac{1}{n} \frac{i}{n} \ln \left ( \frac{n}{i} \right) \\ \left [ -\frac12 x^2 \ln x + \frac14 x^2 \right]_0^1 &= \lim_{n \to \infty} \sum_{i=1}^n \frac{1}{n} \frac{i}{n} \ln \left ( \frac{n}{i} \right) \\ \frac{1}{4} &=\lim_{n \to \infty} \frac{1}{n^2} \sum_{i=1}^n \l i \ln n - i \ln i \r \\ &= \lim_{n \to \infty} \frac{1}{n^2}\l \frac{n(n+1)}{2} \ln n - \sum_{i=1}^n i \ln i \r \\ &= \lim_{n \to \infty} \l \frac{1}{2}(1+\frac{1}n) \ln n - \frac{1}{n^2}\sum_{i=1}^n i \ln i \r \\ &= \lim_{n \to \infty} \l \frac{1}{2}(1+\frac{1}n) \ln n - \frac{1}{n^2}\sum_{i=1}^n \sum_{k=1}^i \ln i \r \\ &= \lim_{n \to \infty} \l \frac{1}{2}(1+\frac{1}n) \ln n - \frac{1}{n^2}\sum_{k=0}^{n-1} \sum_{i=0}^k \ln (n-i) \r \\ &= \lim_{n \to \infty} \l \frac{1}{2}(1+\frac{1}n) \ln n - \frac{1}{n^2}\sum_{k=0}^{n-1} \ln \frac{n!}{(n-k)!}\r \\ \end{align*}

---

Solution:

1. \begin{align*} && \frac1{1-x} &= \sum_{r=0}^{\infty} x^r \\ \underbrace{\Rightarrow}_{\frac{\d}{\d x}} && \frac{1}{(1-x)^2} &= \sum_{r=0}^\infty rx^{r-1} \\ \underbrace{\Rightarrow}_{x = \frac12} && 4 &= \sum_{r=0}^{\infty} \frac{r}{2^{r-1}} \end{align*}
2. \begin{align*} && \frac1{1-x} &= \sum_{r=1}^{\infty} x^{r-1} \\ \underbrace{\Rightarrow}_{\int} && -\ln (1-x) &= \sum_{r=1}^{\infty} \frac1{r} x^r \\ \underbrace{\Rightarrow}_{x = \frac12} && \ln 2 &= \sum_{r=1}^{\infty} \frac1{r } \times \frac{1}{ 2^{r}} \\ \Rightarrow && 2 \ln 2 &= \sum_{r=1}^{\infty} \frac1{r } \times \frac{1}{ 2^{r-1}} \\ \end{align*}
3. \begin{align*} && (1-x)^{-1/2} &= 1 + \frac{(-\tfrac12)}{1!} (-x) +\frac{(-\tfrac12)(-\tfrac32)}{2!}(-x)^2 + \cdots \\ &&&= \sum_{r=0}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdots \cdot (2r-1)}{2^rr!} x^r \\ \underbrace{\Rightarrow}_{x = \frac23} && \sqrt{3} &= \sum_{r=0}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdots \cdot (2r-1)}{r!} \frac1{3^r} \\ &&&= 1 + \frac{1}{1!} \frac23 + \frac13 \sum_{r=2}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdots \cdot (2r-1)}{r!} \frac1{3^{r-1}} \\ \Rightarrow && 3\sqrt{3}-5 &= \sum_{r=2}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdots \cdot (2r-1)}{r!} \frac1{3^{r-1}} \\ \end{align*}

---

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:

1. \(M(0) = 0\) since if there's no space on the shelf, we wont be able to put any books on the shelf.
2. If the shelf has length \(1\) it can only fit a thin book. For a thin book to be placed on the shelf, the very first book which comes to be placed must be thin. But this happens with probability \(q\). Therefore \(M(1) = q\).
3. Suppose no books have been placed on the shelf, then with probability \(p\) a large book gets placed on the shelf, and the expected number of books to be placed on the shelf is equivalent to how many books will be placed on the shelf if the shelf only had \(n-2\) spaces. This is \(M(n-2)\). Similar if the book which arrives first is thin (with probability \(q\)) then there will be \(M(n-1)\) more books placed on the shelf in expectation. We've just added \(1\) more book, therefore \(M(n) = 1+pM(n-2) + qM(n-1)\) or rearranging \(M(n) - qM(n-1) - pM(n-2) = 1\).

Suppose \(M(n) = (-p)^n\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= (-p)^n - (1-p)(-p)^n - p(-p)^{n-2} \\ &= (-p)^{n-2}(p^2+(1-p)p-p) \\ &= 0 \end{align*} Suppose \(M(n) = B\), notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= B - (1-p)B - pB \\ &= 0 \end{align*} Finally, if \(M(n) = Cn\) notice that: \begin{align*} M(n) - qM(n-1) - pM(n-2) &= Cn - (1-p)C(n-1) - pC(n-2) \\ &= C(n(1-(1-p)+p)+(1-p)+2p) \\ &= C(1+p) \end{align*} Therefore if \(C = \frac{1}{1+p}\) we have that: \(M(n) = A(-p)^n + B + Cn\) satisfies our recurrence. We also need \(M(0) = 0\) and \(M(1) = q\) \begin{align*} 0 &= M(0) \\ &= A + B \\ 1-p &= M(1) \\ &= -pA+B \end{align*} \((1+p)A = p-1 \Rightarrow A = \frac{p-1}{1+p}, B = \frac{1-p}{1+p}\). Therefore: \[ M(n) = -\frac{1-p}{1+p}(-p)^n + \frac{1-p}{1+p} + \frac{n}{1+p} \] is a possible solution to this equation

---

Solution: Let \(S = \log_{2}\mathrm{e}-\log_{4}\mathrm{e}+\log_{16}\mathrm{e}-\ldots+(-1)^{n}\log_{2^{2^{n}}}\mathrm{e}+\ldots\) then \begin{align*} S &= \sum_{n=0}^{\infty} (-1)^n \log_{2^{2^n}} e \\ &= \sum_{n=0}^{\infty} (-1)^n \frac{\log e}{\log {2^{2^n}}} \\ &= \sum_{n=0}^{\infty} (-1)^n \frac{\log e}{2^n\log {2}} \\ &= \frac{\log e}{\log 2} \sum_{n=0}^{\infty} \frac{(-1)^n}{2^n} \\ &= \frac{1}{\log_e 2} \frac{1}{1+\frac12} \\ &= \frac{1}{\ln (2^{3/2})} \\ &= \frac{1}{\ln (2 \sqrt{2})} \end{align*}

---

Solution:

1. If we can show that \(0 < a - \sqrt{a^2-b} < 1\) then we will be done, since raising a number in \([0,1)\) to a positive integer power will always remain in the same interval. Clearly \(\sqrt{a^2-b} < \sqrt{a^2} = a\) so we have \(a-\sqrt{a^2-b} > 0\) We also have that \(\sqrt{a^2-b} > \sqrt{a^2-(2a-1)} = (a-1)\). Therefore \(a - \sqrt{a^2-b} < a - (a-1) = 1\) as required.
2. If we can show that \(\l a + \sqrt{a^2-b} \r^n + \l a - \sqrt{a^2-b} \r^n = N -r + s\) is an integer we will be done, since the only integer value \(-r+s\) can be is \(0\). This is easy to see, since \begin{align*} \l a + \sqrt{a^2-b} \r^n + \l a - \sqrt{a^2-b} \r^n &= \sum_{k=0}^n \binom{n}{k}a^{n-k}(\sqrt{a^2-b})^k +\sum_{k=0}^n \binom{n}{k}a^{n-k}(-\sqrt{a^2-b})^k \\ &= \sum_{k=0}^n \binom{n}{k}a^{n-k}\l (\sqrt{a^2-b})^k +(-\sqrt{a^2-b})^k \r \\ \end{align*} But every term where \(k\) is odd in this sum is \(0\) (since they cancel) and ever term where \(k\) is even in this sum is an integer. Therefore the sum is an integer and we're done.
3. \begin{align*} -r^2+rN &= -r(r-N) \\ &= s(r-N) \\ &=- \l a - \sqrt{a^2-b} \r^n \l a + \sqrt{a^2-b} \r^n \\ &= -\l \l a - \sqrt{a^2-b} \r \l a + \sqrt{a^2-b} \r\r^n \\ &= - \l a^2 - a^2+b\r^n \\ &= b^n \end{align*} Therefore \(r^2-rN + b^n = 0\)

Looking at \(\left(8+3\sqrt{7}\right)^{n}\) we have \(a = 8, b = 1\) (since \(8^2 - 1 = 9 \cdot 7\). So we can apply the result of the previous question to see that: \(\left(8+3\sqrt{7}\right)^{n}\) differs from an integer by \(\left(8-3\sqrt{7}\right)^{n}\). \begin{align*} 8-3\sqrt{7} &= \frac{1}{8+3\sqrt{7}} \\ &\approx \frac{1}{8 + 8} \\ &\approx 2^{-4} \end{align*} Therefore it differs by approximation \((2^{-4})^n = 2^{-4n}\)

---

Solution:

1. If \(f(x) = \alpha x\) then \(f^{-1}(x) = \frac{1}{\alpha}x\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - \alpha y]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [(1 - \alpha)^n y^n] \\ && &= (1-\alpha)^n n! y \\ \Rightarrow && y + \sum_{n=1}^{\infty} \frac{1}{n!}\frac{\d^{n-1}}{\d y^{n-1}} [y - \alpha y]^n &= y +\sum_{n=1}^{\infty} (1-\alpha)^ny \\ &&&= y + y\l \frac{1}{1-(1-\alpha)}-1 \r \\ &&&= \frac{1}{\alpha}y \end{align*} Where we can sum the geometric progression if \(|1-\alpha| < 1 \Leftrightarrow 0 < \alpha < 2\)
2. Suppose that \(f(x) = x-\frac14x^3\). We would like to find \(f^{-1}(\frac12)\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - (y+\frac14 y^3)]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [\frac1{4^n} y^{3n}] \\ && &= \frac{1}{4^n} \frac{(3n)!}{(2n+1)!} y^{2n+1} \\ \Rightarrow && f^{-1}(\frac12) &= \frac12 + \sum_{n=1}^{\infty} \frac{1}{4^n} \frac{(3n)!}{n!(2n+1)!} \frac{1}{2^{2n+1}} \\ &&&= \frac12 + \sum_{n=1}^{\infty} \frac{(3n)!}{n!(2n+1)!} \frac{1}{2^{4n+1}} \\ \end{align*} Since when \(n = 0\) \(\frac{0!}{0!1!} \frac{1}{2^{0+1}} = \frac12\) we can include the wayward \(\frac12\) in our infinite sum and so we have the required result.
3. Consider \(f(x) = x - e^{\lambda x}\) we are interested in \(f^{-1}(0)\). \begin{align*} && \frac{\d^{n-1}}{\d y^{n-1}} [y - (y-e^{\lambda y})]^n &= \frac{\d^{n-1}}{\d y^{n-1}} [e^{n\lambda y}] \\ &&&= n^{n-1} \lambda^{n-1}e^{n \lambda y} \\ \Rightarrow && f^{-1}(0) &= \sum_{n=1}^\infty \frac{1}{n!} n^{n-1} \lambda^{n-1} \end{align*} We don't care about convergence, but it's worth noting this has a radius of convergence of \(\frac{1}{e}\) (ie this series is valid if \(|\lambda| < \frac1e\)).

---

Solution: We start by noticing that \(\displaystyle \tan^{-1} t = \int_0^t \frac{1}{1+x^2} \d x\). Consider the geometric series \(1-x^2+(-x^2)^2+ \cdots + (-x^2)^n = \frac{1-(-x^2)^{n+1}}{1+x^2}\). Therefore, \((1+x^2)(1-x^2+(-x^2)^2+ \cdots + (-x^2)^n) = 1-(-x^2)^{n+1}\) or \(1 = (1+x^2)(1-x^2+x^4-\cdots+(-1)^nx^{2n}) +(-1)^{n+1}x^{2n+2}\) \begin{align*} \tan^{-1} t &= \int_0^t \frac{1}{1+x^2} \d x \\ &= \int_0^t \frac{(1+x^2)(1-x^2+x^4-\cdots+(-1)^nx^{2n}) +(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \\ &= \int_0^t (1-x^2+x^4-\cdots+(-1)^nx^{2n})\d x + \int_0^t \frac{(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \\ &= t - \frac{t^3}{3}+\frac{t^5}{5}-\cdots + (-1)^n \frac{t^{2n+1}}{2n+1}+\int_0^t \frac{(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \\ &= \sum_{r=0}^n \frac{(-1)^r t^{2r+1}}{2r+1} + \int_0^t \frac{(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \\ \end{align*} Therefore we can say (for \(0 \leq t \leq 1\)) \begin{align*} \left | \tan^{-1} t - \sum_{r=0}^n \frac{(-1)^r t^{2r+1}}{2r+1} \right | &= \left | \int_0^t \frac{(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \right | \\ &\leq \left | \int_0^t x^{2n+2} \d x \right | \\ &= \frac{t^{2n+3}}{2n+3} \\ \\ \left | \tan^{-1} t - \sum_{r=0}^n \frac{(-1)^r t^{2r+1}}{2r+1} \right | &= \left | \int_0^t \frac{(-1)^{n+1}x^{2n+2}}{x^2+1} \d x \right | \\ &\geq \left | \int_0^t \frac{(-1)^{n+1}x^{2n+2}}{1+1} \d x \right | \\ &= \frac{t^{2n+3}}{2(2n+3)} \\ \end{align*} Since \(\tan^{-1} 1 = \frac{\pi}{4}\) we must have that: \begin{align*} \lim_{n \to \infty} \left | \frac{\pi}{4} - \sum_{r=0}^{n}\frac{(-1)^{r}}{(2r+1)} \right | \to 0 \Rightarrow \lim_{n \to \infty} 4\sum_{r=0}^{n}\frac{(-1)^{r}}{(2r+1)} \to \pi \end{align*} However, \begin{align*} && \left | 4\sum_{r=0}^{n}\frac{(-1)^{r}}{(2r+1)} - \pi \right | &\geq 4 \frac{1}{2(2n+3)} \\ && &= \frac{2}{2n+3} \\ \\ && \frac{2}{2n+3} \geq 10^{-2} \\ \Leftrightarrow && 200 \geq 2n+3 \\ \Leftrightarrow && 197 \geq 2n \\ \Leftrightarrow && 98.5 \geq n \\ \end{align*} Therefore we need more than \(98\) terms to get two decimal places of accuracy. Not great!