Challenge Math Challenge - February 2019

Messages
927
Reaction score
484
Time for our new winter challenge! This time our challenge has also two Computer Science related questions and a separate section with five High School math problems. Enjoy!

Rules:

a)
In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
b) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
d) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.
e) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems.
f) High School problems are intended exclusively for High School students. There is no point to be solved by people with higher education, so members are kindly requested to respect this rule as well.

Questions

Recurrence relations and algorithms (Questions ##1## and ##2##)

In the cases that an algorithm includes a recursive call, its running time can be expressed via a recurrence relation or equivalently via an equality or inequality which gives the general term of a sequence as a function of smaller terms.
The main techniques used for solving recurrence relations are

- Guess: We guess the solution and then by substitution and utilizing mathematical induction, we try to prove that we guessed right. This method is used when we don't seek for an exact solution but for finding an upper bound. In many cases a good guess can be found using the recursion tree.

- Iteration method (a.k.a. expansion or unfolding method or repeated substitution): This is a (usually) laborious method as we repeatedly apply the given recurrence relation till we find an easily solvable form.

- Master method: As its name implies, it is a "recipe" for solving recurrence relations of the form
##T(n) = a T(\frac{n}{b}) + f(n),\space\space\space\space a, b \geq 1, f(n) > 0, \forall n \geq n_0## where ##a, b## are constants, ##f(n)## is an asymptotically positive function and the division ##\frac{n}{b}## can be translated as either ##\lfloor \frac{n}{b} \rfloor## or ##\lceil \frac{n}{b} \rceil##. Such recurrence relations are present in the analysis of algorithms that use the divide-and-conquer technique. In rough lines, the solution of a problem amounts to the recursive solution of ##a## sub-problems, each of size ##
\frac{n}{b}## and the combination of these individual solutions. The function ##f(n)## represents the cost of both the segmentation in ##a## sub-problems and the combination of their respective solutions.

##1##. (solved by @lpetrich ) Find an upper bound for the recurrence relation ##T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + 1## using the guess method in an optimal way. If ##T(1) = 4## find the lower bounds for the values of constants.

##2##. (solved by @lpetrich ) Solve the recurrence relation ##T(n) = 2T(\frac{n}{3}) + n##,##\space\space\space\space T(1) = 1##. Assume that ##n## is a power of ##3##.

##3##. (solved by @lpetrich ) Let ##f(x)=\dfrac{(\cos \varphi - \sqrt{3}\sin \varphi +1)x+2\sqrt{3}\sin \varphi}{x^2}##
and ##g(x)=\dfrac{(\cos \varphi - \sqrt{3}\sin \varphi -1)x+2\sqrt{3}\sin \varphi}{x^2}##. For which values of ##\varphi## are ##f \perp g## in ##L^2([1,\infty))\,?##

##4##. (solved by @lpetrich ) Let ##x## be a real number. Find ##\lim_{n\to\infty}n\left(\left(1+x/n\right)^n-e^x\right).##

##5##. a.) (solved by @QuantumP7 ) Compute the last three digits of ##3^{2405}\,.##
##\space\space\space\space##b.) (open) Show that there is an integer ##a \in \mathbb{Z}## such that ##64959\,|\,(a^2-7)\,.##

##6##. (solved by @Periwinkle ) Let ##f: [0,1] \rightarrow \mathbb{R}## be a continuous function with ##f(0) = f(1)## . Prove that the equation ##f(x) = f(x + \frac{1}{n})## has at least one real root, for all ## n = 1, 2, 3,\dots##

##7##. Let ##\zeta## be a primitive ##7##th root of unity. For how many ##(a_1,\ldots,a_6)\in \{0,1\}^6## is it true that ##\mathbb{Q}(a_1\zeta+\ldots+a_6\zeta^6)=\mathbb{Q}(\zeta)\,?##

##8##. (solved by @Periwinkle ) In a conference there are ##n## persons. Show that there are two persons such that, from the rest ##n - 2## persons, there are at least ##\lfloor \frac{n}{2} \rfloor - 1## persons each of which knows both the aforementioned two persons or else knows no one of them. Suppose that "know someone" is a symmetric relation.

##9##. Let ##A## be a real square matrix. Show that if ##A-I## is nilpotent, then ##A## has a square root.

##10##. If an ##n \times n## matrix ##A## satisfies ##A^2 - 3 A + 2 \mathbb{I} = \mathbb{O}## where ##\mathbb{I}## is the ##n \times n## identity matrix and ##\mathbb{O}## the ##n \times n## zero matrix, prove that for all positive integers ##n \geq 1## holds ##A^{2n} - (2^n + 1)A^n + 2^n \mathbb{I} = \mathbb{O}##.

HS.jpg


##1##. (solved by @Leo Consoli ) A man wants to figure out the length of an escalator, i.e. the number of steps ##[N]## if it was out of order. Since it wasn't out of order, he counted ##60## steps if he walks with the stairs and ##90## steps if he walks in the opposite direction. What is ##[N]?##

##2##. (solved by @Young physicist ) We are looking for a number with eight digits: two of each ## 1,2,3,4##. The ones are separated by one other number, the twos by two, the threes by three, and the fours by four other numbers.

##3##. (solved by @archaic ) Which of you four threw the ball in my window?
##A## says: It was ##E##.
##E## says: It was ##G##.
##F## says: It was not me.
##G## says: ##E## lied
a.) If only one of the four lied, who threw the ball?
b.) If only one person has told the truth, who was the culprit?

##4##. (solved by @Ujjwal Basumatary ) Choose any two but different natural numbers and form their sum, their difference and product. Prove that among these three numbers at least one is divisible by ##3##.

##5##. (solved by @Leo Consoli ) Prove that the remainder in dividing any prime by ##30## is either ##1## or prime again. Is this also true when dividing a prime number by ##60\,?##
 

Attachments

  • HS.jpg
    HS.jpg
    1.7 KB · Views: 485
Last edited by a moderator:
  • Like
Likes Periwinkle, atyy, Greg Bernhardt and 4 others
Physics news on Phys.org
High school 2:
41312432

I found that literally by trial and error though, not sure what the proper method is.

The only “ method” I use is that because 4 has to be separated by 4 numbers, the are only 3 possible positions, which I then can trial and error easier.
 
  • Like
Likes atyy
YoungPhysicist said:
High school 2:
41312432

I found that literally by trial and error though, not sure what the proper method is.

The only “ method” I use is that because 4 has to be separated by 4 numbers, the are only 3 possible positions, which I then can trial and error easier.
Yes, conclusions and exclusions are probably the only way here. However, your answer is not complete.
 
fresh_42 said:
Yes, conclusions and exclusions are probably the only way here. However, your answer is not complete.
More than one answer?
 
Yes.
 
  • Like
Likes YoungPhysicist
YoungPhysicist said:
More than one answer?
Are you still trying to find it? Please do so, for a) it's quite easy and b) an important lesson to learn here!
 
fresh_42 said:
Are you still trying to find it? Please do so, for a) it's quite easy and b) an important lesson to learn here!
Yeah, I am just playing baseball for the past couple hours. I’ll do that as soon as I finished my game.
 
Last edited:
  • Like
Likes atyy
High school 2 second attempt:
23421314 is also correct (wait, isn’t that the first one reversed? Is that the lesson?)
 
  • Like
Likes atyy
YoungPhysicist said:
High school 2 second attempt:
23421314 is also correct (wait, isn’t that the first one reversed? Is that the lesson?)
Yes, it is, at least one half of it. The other half to learn is: do not make hidden assumptions or be satisfied too early! In this case the assumption, that one solution already does it, because the way to find it has left apparently no other possibilities. That's a mathematical standard: There are always two parts: Does a solution exist at all? If so, is it unique?

When it comes to solution spaces, always look out for symmetries! They can make life a lot easier, e.g. to restrict a proof on one case as others are symmetric. They can also show the structure of solutions. O.k. maybe not so much in this simple case, but in general. Symmetries are of extraordinary importance in mathematics as well as in physics. So always look out for symmetries.
 
  • Like
Likes maline, atyy and YoungPhysicist
  • #10
High school 3a:
E lied.

Process:
If A lied, then E lied as well since what G said is the truth. Contradiction.

If E lied, all other statements suggest E is the one throwing the ball.

If F lied, then the one throwing the ball is F, making A and E lying as well. Contradiction.

If G lied, than G is the one throwing the ball, then A lied as well. Contradiction.
 
  • #11
High school 3
a) E lied and is the culprit, else there would be contradictions.
b) G told the truth and F is the culprit, contradictions otherwise.
 
  • Like
Likes atyy and fresh_42
  • #12
3
##<f, g> = 0## with ##<f, g> = \int_1^\infty fgdx##. Since we are in ℝ this operator is bilinear and so:
$$<f, g> = (cos \phi - \sqrt{3} sin \phi + 1)(cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 x, \frac 1 x \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi + 1) \left< \frac 1 x, \frac 1 {x^2} \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 {x^2}, \frac 1 x \right> + (2\sqrt{3} sin \phi)^2 \left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 0$$
Evaluating:
$$\left< \frac 1 x, \frac 1 x \right> = 1$$
$$\left< \frac 1 {x^2}, \frac 1 x \right> = 2$$
$$\left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 3$$
Here I was lazy and I used Mathematica to simplify the above expression, but if that is against the rule please delete this and I will do the calculation by hand. I got:
$$2 sin \phi (3 \sqrt{3} cos\phi+ 7 sin\phi) = 0$$
So ##\phi = k \pi## with ##k = 0, 1, 2...## and ##\phi = -arctan \left( \frac {3 \sqrt{3}} 7 \right) + \frac {k \pi} 2## with ##k = 0, 1, 2...##
 
  • #13
dRic2 said:
3
##<f, g> = 0## with ##<f, g> = \int_1^\infty fgdx##. Since we are in ℝ this operator is bilinear and so:
$$<f, g> = (cos \phi - \sqrt{3} sin \phi + 1)(cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 x, \frac 1 x \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi + 1) \left< \frac 1 x, \frac 1 {x^2} \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 {x^2}, \frac 1 x \right> + (2\sqrt{3} sin \phi)^2 \left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 0$$
Evaluating:
$$\left< \frac 1 x, \frac 1 x \right> = 1$$
$$\left< \frac 1 {x^2}, \frac 1 x \right> = 2$$
$$\left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 3$$
Here I was lazy and I used Mathematica to simplify the above expression, but if that is against the rule please delete this and I will do the calculation by hand. I got:
$$2 sin \phi (3 \sqrt{3} cos\phi+ 7 sin\phi) = 0$$
So ##\phi = k \pi## with ##k = 0, 1, 2...## and ##\phi = -arctan \left( \frac {3 \sqrt{3}} 7 \right) + \frac {k \pi} 2## with ##k = 0, 1, 2...##
I have a different result, but I cannot see whether I did a mistake, which is possible as I constructed the problem myself, or you did, since you neither gave a complete proof nor does your formula fit on the page.

And yes, a complete solution is required, no hidden computer algorithms.

Edit: I have checked my result again, so I think you made a mistake.
 
Last edited:
  • #14
fresh_42 said:
your formula fit on the page.
Yes it does... Scroll to the right and you will see the whole equation.

fresh_42 said:
no hidden computer algorithms.
I just used the command
Code:
Simplfy[ ---copy-paste that long equations---]
Does that mean I have to do it by hand ?
fresh_42 said:
I have a different result
I checked the result I got putting it in the starting functions and I got the expected result, but I could have made some copy/paste mistake myself
 
  • #15
dRic2 said:
I checked the result I got putting it in the starting functions and I got the expected result, but I could have made some copy/paste mistake myself
I double checked it again. Have you checked for ##\pi/6## which is as far as I can see not in your list?
 
  • #16
fresh_42 said:
I double checked it again. Have you checked for π/6π/6\pi/6 which is as far as I can see not in your list?
You are right, ##\pi/6## is a solution I have overlooked. The strange thing is that if I put ##\pi/6## in the equation I wrote in post #12 it doesn't yield zero... but the integral is actually zero. Is there something wrong in my answer ? Are the other results correct ? I maybe be just hitting some wrong keys on the keyboard because it's 3 am here :biggrin::biggrin:
Tomorrow I'll try again. I'm really sorry for all the trouble.
 
  • #17
dRic2 said:
Is there something wrong in my answer ?
I think there has to be. If I made no mistake, then there is an elegant solution of it with not many easy, i.e. polynomial integrals.
 
  • #18
4. Let ##x## be a real number. Find ##\lim_{n \rightarrow \infty}n((1+\frac {x}{n})^{n} - e^{x})##.

Answer:

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

##= \left( \lim_{n \rightarrow \infty}n * e^{x} \right) - \left( \lim_{n \rightarrow \infty}n * e^{x} \right) ##

##=0##
 
  • #19
QuantumP7 said:
##\lim_{n \rightarrow \infty}n((1+\frac {x}{n})^{n} - e^{x}) = \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty}(1+\frac {x}{n})^{n} \right) - \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty} e^{x} \right)##

This is not right, as neither of the terms on your righthand side exist.
 
  • #20
Hi, here is my attempt for high school problem 1:
Being N the number of steps when the escalator is not working, s the size of a step of the escalator and u the speed of the escalator.
In the first situation when the person is going up:
s is the relative velocity to the escalator, and (u+s) is the velocity to the ground, so the movement equation is:
gif.gif

In the second situation:
gif.gif

Dividing both by s:
gif.gif

Adding both sides:
gif.gif
 

Attachments

  • gif.gif
    gif.gif
    511 bytes · Views: 1,423
  • gif.gif
    gif.gif
    499 bytes · Views: 1,386
  • gif.gif
    gif.gif
    1.8 KB · Views: 442
  • gif.gif
    gif.gif
    1.1 KB · Views: 1,401
  • gif.gif
    gif.gif
    1.7 KB · Views: 1,392
  • #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 ##
 
  • #22
QuantumP7 said:
## = \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) ##

This step is not right, as \ln(A-B) is not the same as \ln(A)-\ln(B).
 
  • #23
Infrared said:
This step is not right, as \ln(A-B) is not the same as \ln(A)-\ln(B).

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*
 
  • #24
QuantumP7 said:
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*

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.
 
  • #25
I have a question regarding #2.

What does "Solve the recurrence relation," mean. That is, what kind of presentation would be a solution?
 
  • #26
Buzz Bloom said:
I have a question regarding #2.

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

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.
 
  • #27
QuantumQuest said:
Questions 1 and 2 are about recurrence relations and algorithms.
QuantumQuest said:
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 Θ(n)) of the algorithm whose running time is expressed by the specific recurrence relation.

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:
  • #28
Buzz Bloom said:
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.

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

QuantumQuest said:
Recurrence relations and algorithms (Questions ##1## and ##2##)

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)##.

Buzz Bloom said:
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.

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.

Buzz Bloom said:
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".

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

QuantumQuest said:
In the cases that an algorithm includes a recursive call, its running time can be expressed via a recurrence relation or equivalently via an equality or inequality which gives the general term of a sequence as a function of smaller terms.

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.

Buzz Bloom said:
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.

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:
  • Like
Likes Buzz Bloom
  • #29
QuantumQuest said:
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.
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
 
  • #30
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:
  • #31
Buzz Bloom said:
What is the solution of this recursive series?

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.
 
  • #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##.
 
  • #33
QuantumP7 said:
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##.
Why?
 
  • #34
fresh_42 said:
Why?

##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:
  • #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).
 
  • #36
QuantumP7 said:
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).
##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
QuantumP7 said:
##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.
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.
 
  • #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.
 
  • #38
archaic said:
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?)

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

archaic said:
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

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

Also, is it necessary to use induction?
 
  • #39
fresh_42 said:
##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.

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.
 
  • #40
QuantumQuest said:
or something more specific?
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)

QuantumQuest said:
Also, is it necessary to use induction?
To put it sarcastically, "I'm a simple man, I see ##n## I use induction".
 
  • #41
archaic said:
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)

As you already know, mathematical induction is a mathematical proof technique that is used to prove that some property ##P(n)## holds true for every natural number. I think that the key here is to understand what is induction exactly and do as many examples / exercises as you can. This will vastly help you gain the required momentum in order to recognize where is induction needed and apply the concept correctly. There is a multitude of examples you can find using a simple google search. Also, you can take a look at this cmu.edu https://www.cs.cmu.edu/~adamchik/21-127/lectures/induction_1_print.pdf for some problems beyond the usual (very basic) ones - it is Computer Science notes so it has some relevant to CS examples.

archaic said:
To put it sarcastically, "I'm a simple man, I see ##n## I use induction".

Mathematical induction is a very important method regarding proofs but (obviously) it is not a litmus test. For this particular question, I would hint to think of the problem in terms of functions i.e. using mostly Calculus.
 
Last edited:
  • Like
Likes archaic
  • #42
Hi @Infrared:

I gather you are the reviewer for problem #4. I have just completed my second try at a solution in post #30. Please take a look at it and let me know if I made any errors, or if it still needs some additional presentation.

Regards,
Buzz
 
  • #43
Could you please clarify the following step for me? Your answer is close, but it's not quite right (also, you should give a closed form instead of leaving it as an infinite sum).

Buzz Bloom said:
(1/k!)[(1-1/n)+(1-2/n)+...+(1-(n-k+1)]
= (1/k!) [ 1 - (1/n)Σ{j=1,k+1}j + O(1/n2)]


Also, 1+2+\ldots+(k+1)=(k+1)(k+2)/2, not k(k+1)/2, but just fixing this doesn't give the right answer either.
 
  • #44
Infrared said:
1+2+…+(k+1)=(k+1)(k+2)/2
Infrared said:
but just fixing this doesn't give the right answer either.
Infrared said:
it's not quite right (also, you should give a closed form instead of leaving it as an infinite sum).
Hi Infrared:

Thank you very much for your response to my solution attempt. The first error is just carelessness on my part. As an octogenarian I have found that happens much more often than it did a decade or two ago. I will now make an effort to find the second error to make the answer "quite right". It is not immediately obvious to me, but I should be able to find it. I expect that putting the answer into closed form will be the most difficult part of the necessary fix, but I am hopeful that when I find the second error, that step will become easier.

Could you explain a bit what needs clarification in the step
(1/k!)[(1-1/n)+(1-2/n)+...+(1-(n-k+1)]
= (1/k!) [ 1 - (1/n)Σ{j=1,k+1}j + O(1/n2) ]​
I am guessing it is related to O(1/n2), but I am not sure about that.

ADDED
I now see that the sum
(1-1/n)+(1-2/n)+...+(1-(n-k+1)
should be a product. I will also fix that careless error in Post #30.

Regards,
Buzz
 
Last edited:
  • #45
Ujjwal Basumatary said:
High School 5:

It suffices to show that any prime ##p \in \{1, 7, 11, 13, 17, 19, 23, 29\}_{\mod(30)}##. Notice that this is true for otherwise we would always have another prime dividing ##p##. Done.
I cannot follow your argumentation. Could you be a bit more detailed? And what about 60?
 
  • #46
Hi @Infrared:

I believe I have edited post #30 to correct all my errors for solving problem #4, and I think it is now OK. Please take another look at it.

Regards,
Buzz
 
Last edited:
  • #47
Ujjwal Basumatary said:
High school 4:

Let ##a, b## be the two numbers. If anyone of these is divisible by ##3## we are done as ##3## also divides their product. Hence assume that ##3 \nmid a, b##. This implies ##a, b \equiv 1, 2 \mod(3)##. It is easy to see that any choice of ##a, b## such that ##3\nmid a, b## gives either their sum or difference as a multiple of ##3##.
If it is so easy to see, why don't you write it?
 
  • #48
fresh_42 said:
I cannot follow your argumentation. Could you be a bit more detailed? And what about 60?
I have edited my posts. Sorry about the brief post I thought it would be unnecessary to post trivial facts.
 
  • #49
Ujjwal Basumatary said:
I have edited my posts. Sorry about the brief post I thought it would be unnecessary to post trivial facts.
Sloppiness has to be earned. Easy to see, trivial or obvious are not terms I want to see in the high school section, since they all are.
 
Last edited:
  • Like
Likes StoneTemplePython
  • #50
Ujjwal Basumatary said:
High School 5:

It suffices to show that any prime ##p## is congruent modulo ## 1, 3, 7, 11, 13, 17, 19, 23, 29## modulo ##30##. Notice that this is true for otherwise we would always have another prime dividing ##p##. For example if ##p\equiv 6 \mod(30)## we would have ##6## divide ##p##.
Why does ##30 \,|\, (p-6) ## imply ##6\,|\,p\,?## Sorry, but this needs an explanation. As it stands, it is wrong.
As for ##60##, any prime is congruent to ##1, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59## modulo ##60## and hence the statement holds good. In general a prime ##p## can be congruent to only ##1## or another prime ##q## modulo a composite number ##a## such that ##q \nmid a##
Same here. Why are only those primes possible remainders? I do not need a solution, I have a better one, but you should demonstrate your reasoning on a high school level. And you did not answer the question: what about ##60##? What does "holds good" mean?
 

Similar threads

2
Replies
80
Views
9K
2
Replies
93
Views
14K
Replies
42
Views
10K
2
Replies
69
Views
8K
3
Replies
100
Views
11K
2
Replies
67
Views
11K
2
Replies
86
Views
13K
2
Replies
61
Views
11K
3
Replies
114
Views
10K
Replies
39
Views
12K
Back
Top