Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Featured Challenge Math Challenge - February 2019

Tags:
  1. Feb 7, 2019 #21
    4. Let x be a real number. Find ## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##

    Answer:

    ##\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 #22

    Infrared

    User Avatar
    Gold Member

    This step is not right, as [itex]\ln(A-B)[/itex] is not the same as [itex]\ln(A)-\ln(B)[/itex].
     
  3. Feb 7, 2019 #23
    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)##

    Answer:
    ## \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 #24

    Infrared

    User Avatar
    Gold Member

    You can't do this, because [itex]0\cdot\infty[/itex] is an indeterminate form and so doesn't always evaluate to zero. This is rather like claiming that [tex]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.[/tex]

    For what it's worth, the answer is not zero or infinity. It depends on [itex]x[/itex].
     
  5. Feb 8, 2019 #25

    Buzz Bloom

    User Avatar
    Gold Member

    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 #26

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    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 #27

    Buzz Bloom

    User Avatar
    Gold Member

    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.

    ADDED

    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 #28

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    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 #29

    Buzz Bloom

    User Avatar
    Gold Member

    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 #30

    Buzz Bloom

    User Avatar
    Gold Member

    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.

    ADDED
    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 #31

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    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 #32
    5. a) Find the last 3 digits of ##3^{2405}##

    Answer:
    ##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 #33

    fresh_42

    User Avatar
    2018 Award

    Staff: Mentor

    Why?
     
  14. Feb 9, 2019 #34
    ##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 #35
    5.(b) Show that there is an integer ##a \in \mathbb{Z}## such that 64959| ## (a^{2} - 7)##

    Answer:

    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 #36

    fresh_42

    User Avatar
    2018 Award

    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 #37
    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 #38

    QuantumQuest

    User Avatar
    Science Advisor
    Gold Member

    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 #39
    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 #40
    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".
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?