# FeaturedChallenge Math Challenge - February 2019

Tags:
1. Feb 10, 2019 at 3:02 PM

### QuantumQuest

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.

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: Feb 10, 2019 at 3:15 PM
2. Feb 10, 2019 at 10:32 PM

### Buzz Bloom

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

3. Feb 11, 2019 at 1:58 AM

### Infrared

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

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.

4. Feb 11, 2019 at 7:21 AM

### Buzz Bloom

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: Feb 11, 2019 at 7:50 AM
5. Feb 11, 2019 at 10:58 AM

### Staff: Mentor

6. Feb 11, 2019 at 10:59 AM

### Buzz Bloom

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: Feb 11, 2019 at 11:31 AM
7. Feb 11, 2019 at 11:01 AM

### Staff: Mentor

If it is so easy to see, why don't you write it?

8. Feb 11, 2019 at 11:16 AM

### Ujjwal Basumatary

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

9. Feb 11, 2019 at 11:22 AM

### Staff: Mentor

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: Feb 11, 2019 at 11:30 AM
10. Feb 11, 2019 at 11:29 AM

### Staff: Mentor

Why does $30 \,|\, (p-6)$ imply $6\,|\,p\,?$ Sorry, but this needs an explanation. As it stands, it is wrong.
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?

11. Feb 11, 2019 at 12:02 PM

### Buzz Bloom

Hi QQ:

I get that the "solution" of the Fibonacci number recursive definition is the closed form formula that calculated the value of the nth number in the series. What I do not get is the relationship of this "solution" to algorithms and the time it takes to perform a calculation using an algorithm. hat I am guessing is there are more than one definition for what it means to solve a recursion expression. One meaning is the closed form that represents the nth term of the recursive sequence, and another meaning has something to do with algorithms and time to perform calculations. If I get the time, I will try to read the 30 page article you cited, and perhaps then I will understand this second meaning.

Regards,
Buzz

12. Feb 11, 2019 at 12:19 PM

### Buzz Bloom

I am hoping that someone can educate me the meanings of some notation that was not included in any math courses I took as a math major over 50 years ago.
In the first quote, what does the symbol ⊥ mean, and what does L2([1,∞)) mean?
In the second quote, what does the vertical bar in 64959|(a2−7) mean?
In the third quote, what does special font Q mean in Q(a1ζ+…+a6ζ6)=Q(ζ)?

Regards,
Buzz

13. Feb 11, 2019 at 12:19 PM

### Infrared

@Buzz Bloom I am still concerned by $(1-1/n)\ldots (1-(k+1)/n)=1-\frac{1}{n}(1+2+\ldots+ (k+1))+O(1/n^2)$. I agree that you can expand the lefthand side in powers of $1/n$ and that the first two coefficients are what you have written. But the coefficients for $1/n^k$ are going to be polynomials in $k$ and $k$ is not bounded independent of $n$ since $k$ can be as large as $n$. For example if your next term was $k^3/n^2$, then for the terms when $k$ is close to $n$, this is $O(n)$.

14. Feb 11, 2019 at 12:34 PM

### Buzz Bloom

Hi Infrared:

Thank you for your reply. You definitely got me. I will have to explore this issue in detail, and it will take quite a while.

Regards,
Buzz

15. Feb 11, 2019 at 6:03 PM

### Infrared

The first two problems aren't mine, but I'm pretty sure the following is intended (and @fresh_42 can clarify what he means if I get it wrong):
$L^2([1,∞))$ means the set of real-valued functions $f$ defined on $[1,\infty)$ such that $\int_1^\infty f(x)^2 dx$ exists and is finite (technically, it is defined as equivalence classes of such functions up to equality almost everywhere, and the integral means the Lebesgue integral instead of the (improper) Riemann integral, but neither of these facts are important to the problem). There is an inner product on this space defined by
$(f,g)=\int_1^\infty f(x)g(x)dx$. Then $f\perp g$ means $(f,g)=0$. Oftentimes, you work with complex-valued functions instead and then the inner product would be $(f,g)=\int_1^\infty f(x)\overline{g(x)}dx$.

The vertical line means "divides". For example, $3\vert 9$ is true but $3\vert 10$ is not.

$\mathbb{Q}$ is the field of rational numbers. If $\alpha$ is an element of some field $K$ that contains $\mathbb{Q}$, then $\mathbb{Q}(\alpha)$ is the smallest subfield of $K$ that contains all elements of $\mathbb{Q}$ as well as $\alpha$. For example, you can check $\mathbb{Q}(\sqrt{2})=\{a+b\sqrt{2}: a,b\in\mathbb{Q}\}$.

16. Feb 11, 2019 at 7:23 PM

### QuantumQuest

I gave you the (explicit) solution because you asked for the solution of the equation i.e. for the $F(n)$.

In any case, what you ask in post #50 is something outside the questions $1$ and $2$ of the challenge themselves but I'll try to explain it as it is something inside the context of these questions.

The explicit solution of the Fibonacci series gives you the $n$-th term of the series. If you want to calculate this by developing / using a program on a computer, you have to implement an algorithm which in this case can be iterative or recursive. The iterative version is based on having a repetition structure (mostly known as a loop) which computes the $n$-th term of the series in an imperative repetition fashion. Now, the formula $F_n = F_{n-1} + F_{n-2}$ for Fibonacci series, gives us a natural example of recursion which can be written as a recursive function like this

Code (Text):
function fib(n) {
if n = 0 return 0
if n = 1 return 1
return fib(n-1) + fib(n-2)
}
In order to measure the time it takes for the above algorithm to execute when implemented as a program, approximately, we are measuring in terms of lines of code. Let $T(n)$ denote the number of steps needed to compute fib(n). If $n \lt 2$ the function runs for just a couple of steps i.e. for $n \leq 1$ we have $T(n) \leq 2$. Now, if $n$ gets larger there are two recursive invocations of the function fib. The time they take is $T(n -1)$ and $T(n - 2)$ respectively. We must also add the time taken for the checks on the value of $n$ and for the final addition. So, we have $T(n) = T(n - 1) + T(n - 2) + 3$ for $n \gt 1$. Now, if we compare this to the recurrence relation for $F_n$ we easily see that $T(n) \geq F_n$. $T(n)$ is exponential in $n$.

In general, any recursive function such as the above gives us a recurrence relation for time: the time for any routine is the time within the routine itself, plus the time for the recursive calls.

17. Feb 11, 2019 at 9:23 PM

### Buzz Bloom

Hi @Infrared and @QuantumQuest:

Thank you both very much for your posts #55 and #56. I feel your posts have taught me some very useful notations and concepts.

Regards,
Buzz

18. Feb 12, 2019 at 9:10 AM

### Buzz Bloom

Hi @Infrared:

I have fixed another error in post #30, but I still have more work to do on it.

Regarding your issue about O(1/n), I have thought about a method to explain why this concept is correct, but I had not yet added that explanation because I have not yet decided on how to present this concept mathematically in the solution. The concept involves the terms (all multiplied by n) of the form
Gj,k(x,n) = aj,k (1/nj) xk/k! for 1<j<k.​
The limit
limn→∞ nGj,k (x,n) = 0​
because the values of aj,k are all finite and are independent of n. Do you think a detailed mathematical explanation of this would be sufficient to fix the solution?

Regards,
Buzz