# FeaturedChallenge Math Challenge - February 2019

Tags:
1. Feb 7, 2019

### QuantumP7

4. Let x be a real number. Find $\lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)$

$\lim_{n \rightarrow \infty} ln \left( n \left( \left(1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)$

$= \lim_{n \rightarrow \infty} \left( ln(n) + ln \left( \left(1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) + ln \left(1 + \frac{x}{n} \right) ^{n} - ln \left( e^{x} \right) \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) \right) + \lim_{n \rightarrow \infty} \left( ln \left(1 + \frac{x}{n} \right) ^{n} - ln \left( e^{x} \right) \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) \right) + \lim_{n \rightarrow \infty} \left( ln \left(1 + \frac{x}{n} \right) ^{n} \right) - \lim_{n \rightarrow \infty} \left( ln \left( e^{x} \right) \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) \right) + \left( x \right) - \lim_{n \rightarrow \infty} \left( x \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) \right) + \left( x \right) - \left( x \right)$
$= \lim_{n \rightarrow \infty} \left( ln(n) \right)$
$= \infty$

2. Feb 7, 2019

### Infrared

This step is not right, as $\ln(A-B)$ is not the same as $\ln(A)-\ln(B)$.

3. Feb 7, 2019

### QuantumP7

Aw. You're right.

4. Let x be a real number. Find $\lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)$

$\lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)$
$= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)$
$= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right) ^{n} - \lim_{n \rightarrow \infty} \left( e^{x} \right) \right)$
$= \left( \lim_{n \rightarrow \infty} n \right) \left( e^{x} - e^{x} \right)$
$= \left( \lim_{n \rightarrow \infty} n \right) \left( 0 \right)$
$= 0$

Am I getting closer? *hopeful smile*

4. Feb 7, 2019

### Infrared

You can't do this, because $0\cdot\infty$ is an indeterminate form and so doesn't always evaluate to zero. This is rather like claiming that $$1=\lim_{x\to\infty} 1=\lim_{x\to\infty} \left(x\cdot\frac{1}{x}\right)=\left(\lim_{x\to\infty} x\right)\left(\lim_{x\to\infty}\frac{1}{x}\right)=\left(\lim_{x\to\infty} x\right)\cdot 0=0.$$

For what it's worth, the answer is not zero or infinity. It depends on $x$.

5. Feb 8, 2019

### Buzz Bloom

I have a question regarding #2.

What does "Solve the recurrence relation," mean. That is, what kind of presentation would be a solution?

6. Feb 8, 2019

### QuantumQuest

Questions $1$ and $2$ are about recurrence relations and algorithms. So,- as a recurrence relation can be used to express the running time of an algorithm, by solving a recurrence relation we can find what $T(n)$ says about $O(n)$ and / or $\Theta (n)$ depending on the case at hand.

Now, for $2$, I ask for solving the specific recurrence relation - you can check the spoiler for a brief summary of the methods used if needed, which means finding a form that is more general including variable(s) for which, applying the right condition(s), you can reach a conclusion about the $O(n)$ (or maybe $\Theta (n)$) of the algorithm whose running time is expressed by the specific recurrence relation.

7. Feb 8, 2019

### Buzz Bloom

Hi QQ:

Thank you for your response to my post.

I must confess that I had no expectation that the problem statement involved (1) any algorithms, (2) the behavior of O(n) (or maybe Θ(n)), or (3) running time.
My experience with the O(n) notation is limited to its use with an infinite sum to represent the order of magnitude of the sum of remaining terms in the sum following some specific terms. I do not see what it has to do with the recursion. I also have never seen before the Θ(n) notation.

I did scan the thread quickly and failed to find a spoiler for problem #2. I will now make a more careful perusal.

The spoiler you were referring to was the one included in the OP following the rules. I read through it and found no definition of what is means to "solve" a recursion. Please post a definition of the meaning of "the solution of a recursion".

Also, I am unfamiliar with the notation involving a pair of brackets in the shape of an "L" and its mirror image. Please also post an explanation of this notation.

Regards,
Buzz

Last edited: Feb 8, 2019
8. Feb 8, 2019

### QuantumQuest

The problem statement does not speak explicitly about algorithms but the problem is under the title

so it is evidently about recurrence relations as used in the context of algorithms, so we're talking about the running time of an algorithm - that's the $T(n)$ in the recurrence relation(s), and so we have to do with $O(n)$ and $\Theta(n)$.

You can take a look at Wikipedia's Big O Notation.

The $T(n)$ in the given recurrence relation(s) is the running time of an algorithm. By solving the recurrence relation and by the appropriate substitutions after that, you can find bound(s) i.e. $O(n)$, $\Theta(n)$ etc. I hope that this explains what has $O(n)$ to do with the recursion (expressed via a recurrence relation). As for the $\Theta(n)$ notation take a look at this fsu.edu page for instance.

Yes, that's the spoiler I meant. What I talk about there is methods about solving recurrence relations. As I say there,

Now, about solving a recurrence relation, I give the methods used but (obviously) I can not explain here the whole thing from scratch. You can take a look at this cmu.edu page for instance and also google it for much more.

I think that it is widely known - if I am mistaken about this I apologize in advance, that this is the floor function.

Last edited: Feb 8, 2019
9. Feb 8, 2019

### Buzz Bloom

Hi QQ:

Thank you very much for answering my questions.

I took a look at the cmu.edu page you cited, and the 30 page document looks somewhat daunting. It will take some time for me to grasp the relationship between (1) the solution being the estimate of how much time a recursive algorithm takes to execute a calculation given the value of an argument., and (2) solving a recursive function which is somehow related to such an algorithm.

Perhaps you can help me gain an insight by advising me regarding a simple recursive function. For this example I have chosen the
Fibonacci numbers as a recursive function.

F(0) = F(1) = 1
For n>1, F(n) = F(n-1) + F(n-2)

What is the solution of this recursive series?

Regards,
Buzz

10. Feb 8, 2019

### Buzz Bloom

Re #4.
I have now completed my work on a second solution.
I apologize for not using LaTex, but the reference I have does not e.g. help me with finite summations.
I have fixed the first error @Infrared pointed out to me in his post #42, and a second error involving a sum that should be a product. I will be working on the other issues he included for a while.

I found that I had made an error regarding the number of factors (1-1/n)(1-2/n)... . There should be only k-1 factors rather than k+1 factors. I have edited the math to reflect correcting this error.
The problem is to find
S(x) = limn→∞ n((1+x/n)n−ex).​
Using the Binomial Theorem gives:
(1+x/n)n = Σ{k=0,n} C(n,k) (x/n)k
where
C(n,k) = n!/(k! (n-k)!) ,​
and
C(n,k)/nk = (1/k!)[(1-1/n)(1-2/n)...(1-(n-k+1)/n]
= (1/k!) [ 1 - (1/n)Σ{j=1,k-1}j + O(1/n2)]
= (1/k!) [ 1 - (1/n) k(k-1)/2 + O(1/n2)]
= 1/k! - (1/k!)(1/n) k(k-1)/2 + O(1/n2)]
Now break S(x) into three parts.
S(x) = S1(x) + S2(x) + S3(x)

S1(x) = limn→∞ n [ Σ{k=0,n} xk/k! - ex ]
= n [ Σ{k=0,∞} xk/k! - ex ] = 0

S2(x) = - limn→∞ n Σ{k=0,n} (1/n) (k(k-1)/2) xk/k!
= - Σ{k=0,∞} (k2-k)/2 xk/k!

S3(x) = limn→∞ n O(1/n2) = 0​

Therefore the solution is
S(x) = S2(x)
= (1/2) (-x2 + x) ex

Last edited: Feb 12, 2019
11. Feb 8, 2019

### QuantumQuest

Although I think that you can find it easily on the net, in any case, the explicit solution to the Fibonacci recurrence is $F_n = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n$ known as Binet's formula.

12. Feb 9, 2019

### QuantumP7

5. a) Find the last 3 digits of $3^{2405}$

$3^{2405} = \left( 3^{5} \right) ^{481} = \left( 3^{5} \right) ^{400+80+1}$
The last 3 digits of $3^{2405}$ will then be $\left(3^{5} \right)^{1} = 243$.

13. Feb 9, 2019

### Staff: Mentor

Why?

14. Feb 9, 2019

### QuantumP7

$3^{2405} = 3^{5+2400} = (3^{5})(3^{2400})$
$3^{400} \equiv 1(mod 1000)$ so $3^{2400} \equiv 1(mod 1000)$
Then, $3^{2405} = (3^{5})(3^{2400}) \equiv (243*1)(mod 1000)$, so that the last 3 digits of $3^{2405}$ are 243.

Last edited: Feb 9, 2019
15. Feb 9, 2019

### QuantumP7

5.(b) Show that there is an integer $a \in \mathbb{Z}$ such that 64959| $(a^{2} - 7)$

We can see that 3 divides 64959 because its digits add up to a multiple of 3 (6+4+9+5+9 = 33 = 3+3=6). (If necessary, I can explain why. Just let me know.) So, we need to find an integer a such that $a^{2}-7$ is a number that is 3 or 3 x $10^{n}$. Honestly, I brute forced this, and came up with a = 2. $2^2-7 = 4-7=-3$ which definitely divides 64959 (64959 = -3 * -21653).

16. Feb 9, 2019

### Staff: Mentor

$3\,|\,64959$ but not the other way around. The key words here are the Legendre symbol and the Chinese remainder theorem.

As of part 5.a.), your solution
is correct, but a hint to Euler's theorem would have been fine:
$$3^{\varphi(n)} \equiv 1 \,\operatorname{mod} n \\[12pt] \varphi(1000) = \# \text{ numbers from 1 to 1000 which are relatively prime to 1000 } = \varphi(8) \varphi(125)=\varphi(2^3) \varphi(5^3)=2^3 \left(1- \dfrac{1}{2} \right) 5^3 \left(1- \dfrac{1}{5} \right) = 400$$
and thus $3^{400} \equiv 1 \,\operatorname{mod} 1000$ is the information which really counted.

17. Feb 9, 2019

### archaic

Well, since there's an integer $n$ this looks like induction. (I know this isn't a nice way to spot induction, do you please know a website/paper/pdf which talks about the matter?)
What jumps to me is this :
For $n=1$ we have $f(x)=f(x+\frac{1}{n})=f(x+1)$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=2$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=3$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=f(x+\frac{3}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
...
For $n=n$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=...=f(x+\frac{n}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=n+1$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=...=f(x+\frac{n}{n})=f(x+\frac{n+1}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
I am unsure about the last two line and I do not know how to proceed from the first lines.

18. Feb 9, 2019

### QuantumQuest

Do you mean a resource talking about induction in general or something more specific?

This is not correct. Check again this (and the lines below it).

Also, is it necessary to use induction?

19. Feb 9, 2019

### QuantumP7

Thank you, sir! Even though I misread part b, I knew that there was some deeper theory and a more elegant solution that I was unaware of. If no one else attempts part b within a few days, then I will redo it, myself.

I look like a complete idiot in this thread, but I really am learning a lot.

20. Feb 10, 2019

### archaic

Yes, on how to recognize it and why it works. (a farmer which has $n+1$ sheeps of which $n$are black doesn't imply all are, I probably have a very shallow understanding of it)

To put it sarcastically, "I'm a simple man, I see $n$ I use induction".