# Math Challenge - February 2019

• Challenge
• Featured
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?
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.

Buzz Bloom
Gold Member
Questions 1 and 2 are about recurrence relations and algorithms.
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.

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:
Gold Member
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

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

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.

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,

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.

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:
Buzz Bloom
Buzz Bloom
Gold Member
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

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

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:
Gold Member
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.

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

fresh_42
Mentor
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##.
Why?

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

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

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.

Gold Member
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?

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?

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

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)

Also, is it necessary to use induction?
To put it sarcastically, "I'm a simple man, I see ##n## I use induction".

Gold Member
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 page for some problems beyond the usual (very basic) ones - it is Computer Science notes so it has some relevant to CS examples.

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:
archaic
Buzz Bloom
Gold Member
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

Infrared
Gold Member
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).

(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.

Buzz Bloom
Gold Member
1+2+…+(k+1)=(k+1)(k+2)/2
but just fixing this doesn't give the right answer either.
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.

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:
fresh_42
Mentor
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.

Buzz Bloom
Gold Member
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:
fresh_42
Mentor
High school 4:

Let ##a, b## be the two numbers. If any one 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?

I have edited my posts. Sorry about the brief post I thought it would be unnecessary to post trivial facts.

fresh_42
Mentor
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:
StoneTemplePython
fresh_42
Mentor
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?