Exercise from discuss.com.hk (2)

Problem:

$ \lim\limits_{n \to \infty}\sum\limits_{k = 1}^{n - 1}\frac{k}{2^k(n - k)} $

Solution:

Let $ p = n - k $, so we have

$ \begin{eqnarray} & & \sum\limits_{k = 1}^{n - 1}\frac{k}{2^k(n - k)} \\ &=& \sum\limits_{p = 1}^{n - 1}\frac{(n-p)}{2^{n-p} p} \\ &=& \frac{1}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{(n-p)}{2^{-p} p} \\ &=& \frac{1}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{(n-p)2^p}{ p} \\ &=& \frac{1}{2^n}\sum\limits_{p = 1}^{n - 1}\left(\frac{n 2^p}{p} -\frac{p 2^p}{p}\right) \\ &=& \frac{1}{2^n}\sum\limits_{p = 1}^{n - 1}\left(\frac{n 2^p}{p} -2^p\right) \\ &=& \frac{n}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{2^p}{ p}-\frac{1}{2^n}\sum\limits_{p = 1}^{n - 1}2^p \\ &=& \frac{n}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{2^p}{ p}-\frac{1}{2^n}(2^n - 1) \\ &=& \frac{n}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{2^p}{ p}- 1 + \frac{1}{2^n} \\ \end{eqnarray} $

Notice the first term look very much like the previous post, so we will use the same trick to solve the problem, let $ L(n) = \frac{n}{2^n}\sum\limits_{p = 1}^{n - 1}\frac{2^p}{ p} $

$ \begin{eqnarray} & & L(n + 1) \\ &=&\frac{n+1}{2^{n + 1}}\sum\limits_{p = 1}^{n}\frac{2^p}{ p} \\ &=&\frac{n+1}{2^{n + 1}}\left(\sum\limits_{p = 1}^{n-1}\frac{2^p}{ p} + \frac{2^n}{n}\right) \\ &=&\frac{n+1}{2^{n + 1}}\sum\limits_{p = 1}^{n-1}\frac{2^p}{ p} + \frac{n + 1}{2n} \\ &=&\frac{n+1}{2^{n + 1}}\frac{2^n}{n}\frac{n}{2^n}\sum\limits_{p = 1}^{n-1}\frac{2^p}{ p} + \frac{n + 1}{2n} \\ &=&\frac{n+1}{2^{n + 1}}\frac{2^n}{n}L(n) + \frac{n + 1}{2n} \\ &=&\frac{n+1}{2n}L(n) + \frac{n + 1}{2n} \end{eqnarray} $

Again, assume the limit exists, taking limits on both sides, we get

$ \begin{eqnarray} L &=& \frac{1}{2}L + \frac{1}{2} \\ 2L &=& L + 1 \\ L &=& 1 \end{eqnarray} $

Therefore the overall solution is simply 1 - 1 = 0.

Exercise from discuss.com.hk (1)

Problem:

$ \lim\limits_{n \to \infty} \frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^k}{k} $.

Solution:

Let $ L(n) = \frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^n}{n} $

$ \begin{eqnarray} & & L(n + 1) \\ &=& \frac{n + 1}{2^{n + 1}}\sum\limits_{k = 0}^{n + 1}\frac{2^k}{k} \\ &=& \frac{n + 1}{2^{n + 1}}\left(\sum\limits_{k = 0}^{n}\frac{2^k}{k} + \frac{2^{n + 1}}{n + 1}\right) \\ &=& \frac{n + 1}{2^{n + 1}}\sum\limits_{k = 0}^{n}\frac{2^k}{k} + 1 \\ &=& \frac{n + 1}{2^{n + 1}}\frac{2^n}{n}\frac{n}{2^n}\sum\limits_{k = 0}^{n}\frac{2^k}{k} + 1 \\ &=& \frac{n + 1}{2^{n + 1}}\frac{2^n}{n}L(n) + 1 \\ &=& \frac{n + 1}{2n}L(n) + 1 \end{eqnarray} $

Assuming we know that the limit exists, we can simply take limits on both sides to get:

$ L = \frac{1}{2}L + 1 $

That gives the easy answer $ L = 2 $.

Mathematical Analysis - Exercise 1.3

Problem:

Solution:

Suppose $ n = ab $ is not prime, then we can write $ 2^{ab} = (2^{a})^b $. Applying the identity we just proved in the previous problem, we have:

$ 2^{ab} - 1 =  (2^{a})^b - 1 =  (2^{a})^b - 1^b = (2^a - 1)(\cdots) $.

Therefore if $ a \ne 1 $, we have a non-trivial factor for $ 2^{ab} - 1 $.

The contradiction show $ n $ has to be prime.

Mathematical Analysis - Exercise 1.2

Problem:

Solution:

The right hand side sounds like something we can telescope, let's see:

$ \begin{eqnarray*} & & (a - b)\sum\limits_{k = 0}^{n-1}{a^{k}b^{n-1-k}} \\ &=& a\sum\limits_{k = 0}^{n-1}{a^{k}b^{n-1-k}} - b\sum\limits_{k = 0}^{n-1}{a^{k}b^{n-1-k}} \\ &=& \sum\limits_{k = 0}^{n-1}{a^{k+1}b^{n-1-k}} - \sum\limits_{k = 0}^{n-1}{a^{k}b^{n-k}} \\ &=& (a^n + \sum\limits_{k = 0}^{n-2}{a^{k+1}b^{n-1-k}}) - (\sum\limits_{k = 1}^{n-1}{a^{k}b^{n-k}} + b^n ) \\ &=& (a^n + \sum\limits_{k = 1}^{n-1}{a^{k}b^{n-k}}) - (\sum\limits_{k = 1}^{n-1}{a^{k}b^{n-k}} + b^n ) \\ &=& a^n - b^n \end{eqnarray*} $

Mathematical Analysis - Exercise 1.1

Problem:

Solution:

Suppose there exists a largest prime, that means there is only finite number of primes. Consider the product of them plus 1. This number cannot be a prime number because it is larger than the largest prime.

Now consider its prime factorization. Note that when this number is divided by any prime, the remainder 1, therefore, there is just no way of prime factorizing it, contradicting the fundamental theorem of arithmetic, therefore there is no largest prime!