Challenge Math Challenge - September 2019

[Not anonymous]

Yes, $1$ isn't considered a factor, since you can always multiply as many units as you want and get any number of factors. Btw. $-1$ is also a unit, so you could argue that $-1,1,3,-3$ are four odd factors of $6$. It simply makes no sense to allow units.

You're thinking way too complicated. Just calculate $n=r+(r+1)+\ldots + (r+k)$ and examine the factors.

Thanks to @fresh_42 for the hint! The answer is too obvious after that. I merely add some formalism for the sake of completeness. Before my earlier attempt, I had briefly considered working backward from the formula for sum of sequence as suggested by the hint but didn't proceed along that line as I thought I could arrive at a more "intuitive" solution that didn't need formulae, and that made giving a proof more complex that needed.

(11. Show that the number of ways to express a positive integer $n$ as the sum of consecutive positive integers is equal to the number of odd factors of $n$.)

Spoiler: Question 11

Any sequence of $k$ consecutive integers can be written as $a+1, a+2, ..., a+k$. Here $a+1$ is the 1st integer in the sequence. The sum of this sequence is $ka + \frac {k(k+1)} {2} = k(a + \frac {k+1} {2})$. We consider positive integer values for $k$, i.e. $k \in \{2, 3, 4, .., \}$ (since $k$ is the length of a non-empty sequence, it must be a positive integer). We ignore $k=1$ as that will correspond to the degenerate case of single-element sequence $(n)$, whereas the question apparently considers only sequences having more than 1 integer (except when $n$ itself is 1, in which case there is exactly one sequence satisfying the criteria, $\{1\}$).

• We inspect values of $k \in \{2, 3, .., \}$ and look for the value of $a$ such that the sum of the sequence $a+1, a+2, .., a+k$ sums to $n$, i.e. $$k(a + \frac {k+1} {2}) = n$$.
• If $k$ is NOT a factor of $n$, then $(a + \frac {k+1} {2})$ would be non-integer in the above equation, implying that there is no integer $a$ such that a $k$-length integer sequence will add up to $n$, so we only need to consider those values of $k$ that are factors of $n$.
• If $k$ is even, then $\frac {k+1} {2}$ would be a non-integer, so again (even if that $k$ is a factor of $n$), there would be no $k$-length integer sequence that adds up to $n$
• If $k$ is an odd factor of $n$, then $\frac {k+1} {2}$ is an integer and we can find an integer value for $a$ such that the $k$-long sequence starting at $a+1$ adds up to $n$. $a$ is given by the equation $$a = \frac {n} {k} - \frac {k+1} {2}$$
• The value of $a$ from the above equation could be negative, whereas we want only sequences that consist of positive integers alone. It is easy to show that any integer sequence $a+1, a+2, .. a+k$ that adds up to a positive value can be reduced to a positive integer sub-sequence if the original sequence starts with zero or a negative integer
  • If the sequence starts with 0, will simply drop that as removing 0 does not alter the sum of the sequence​
  • If the sequence starts with a negative number and yet adds up to a positive number, then it must be the case that the sequence is of the form $-x, -x+1, -x+2, ..., 0, 1, .., x, x+1, .., x+j$ (for some positive integers $x, j$ satisfying the condition $x = -(a+1)$, $x+j = (a+k)$), i.e. for every negative integer $-y$, the sequence should also contain the positive integer $y$ and the number of positive integers in the sequence should exceed the number of negative integers in the sequence. In effect, the negative integers get canceled out by their positive counterparts in the summation, so we can trim a left portion of original sequence and get a positive-integers-only sequence ($(x+1, x+2, ..., x+j)$) that adds up to the same value as the original sequence.​

Thus, for every odd-factor $k$ of $n$, we can find a unique sequence of consecutive positive integers that sum to $n$ whereas no such sequence would exist for even-factors of $n$. Therefore, the number of ways to express any positive number $n$ equals the number of odd factors of $n$

 

[fresh_42]

Thanks to @fresh_42 for the hint! The answer is too obvious after that. I merely add some formalism for the sake of completeness. Before my earlier attempt, I had briefly considered working backward from the formula for sum of sequence as suggested by the hint but didn't proceed along that line as I thought I could arrive at a more "intuitive" solution that didn't need formulae, and that made giving a proof more complex that needed.

(11. Show that the number of ways to express a positive integer $n$ as the sum of consecutive positive integers is equal to the number of odd factors of $n$.)

Spoiler: Question 11

Any sequence of $k$ consecutive integers can be written as $a+1, a+2, ..., a+k$. Here $a+1$ is the 1st integer in the sequence. The sum of this sequence is $ka + \frac {k(k+1)} {2} = k(a + \frac {k+1} {2})$. We consider positive integer values for $k$, i.e. $k \in \{2, 3, 4, .., \}$ (since $k$ is the length of a non-empty sequence, it must be a positive integer). We ignore $k=1$ as that will correspond to the degenerate case of single-element sequence $(n)$, whereas the question apparently considers only sequences having more than 1 integer (except when $n$ itself is 1, in which case there is exactly one sequence satisfying the criteria, $\{1\}$).

• We inspect values of $k \in \{2, 3, .., \}$ and look for the value of $a$ such that the sum of the sequence $a+1, a+2, .., a+k$ sums to $n$, i.e. $$k(a + \frac {k+1} {2}) = n$$.
• If $k$ is NOT a factor of $n$, then $(a + \frac {k+1} {2})$ would be non-integer in the above equation, implying that there is no integer $a$ such that a $k$-length integer sequence will add up to $n$, so we only need to consider those values of $k$ that are factors of $n$.
• If $k$ is even, then $\frac {k+1} {2}$ would be a non-integer, so again (even if that $k$ is a factor of $n$), there would be no $k$-length integer sequence that adds up to $n$
• If $k$ is an odd factor of $n$, then $\frac {k+1} {2}$ is an integer and we can find an integer value for $a$ such that the $k$-long sequence starting at $a+1$ adds up to $n$. $a$ is given by the equation $$a = \frac {n} {k} - \frac {k+1} {2}$$
• The value of $a$ from the above equation could be negative, whereas we want only sequences that consist of positive integers alone. It is easy to show that any integer sequence $a+1, a+2, .. a+k$ that adds up to a positive value can be reduced to a positive integer sub-sequence if the original sequence starts with zero or a negative integer
  • If the sequence starts with 0, will simply drop that as removing 0 does not alter the sum of the sequence​
  • If the sequence starts with a negative number and yet adds up to a positive number, then it must be the case that the sequence is of the form $-x, -x+1, -x+2, ..., 0, 1, .., x, x+1, .., x+j$ (for some positive integers $x, j$ satisfying the condition $x = -(a+1)$, $x+j = (a+k)$), i.e. for every negative integer $-y$, the sequence should also contain the positive integer $y$ and the number of positive integers in the sequence should exceed the number of negative integers in the sequence. In effect, the negative integers get canceled out by their positive counterparts in the summation, so we can trim a left portion of original sequence and get a positive-integers-only sequence ($(x+1, x+2, ..., x+j)$) that adds up to the same value as the original sequence.​

Thus, for every odd-factor $k$ of $n$, we can find a unique sequence of consecutive positive integers that sum to $n$ whereas no such sequence would exist for even-factors of $n$. Therefore, the number of ways to express any positive number $n$ equals the number of odd factors of $n$

Thus, for every odd-factor $k$ of $n$, we can find a unique sequence of consecutive positive integers that sum to $n$

Where did you show uniqueness?

O.k., it's still too excessive$^*)$ but shows that we get a partition from odd factors. Now couldn't it be, that two factors lead to the same partition, in which case our correspondence wouldn't be one-to-one?

$^*)$ My suggestion had been $2n=2(r+(r+1)+\ldots +(r+k))=(k+1)(2r+k)$ where exactly one factor is odd. Hence an odd factor belongs to a partition. But this doesn't show uniqueness either, which requires a bit more work to do.

 

[Not anonymous]

Where did you show uniqueness?

O.k., it's still too excessive$^*)$ but shows that we get a partition from odd factors. Now couldn't it be, that two factors lead to the same partition, in which case our correspondence wouldn't be one-to-one?

$^*)$ My suggestion had been $2n=2(r+(r+1)+\ldots +(r+k))=(k+1)(2r+k)$ where exactly one factor is odd. Hence an odd factor belongs to a partition. But this doesn't show uniqueness either, which requires a bit more work to do.

To show the uniqueness of the sequence for any given value of $k$, we first show the uniqueness of $a$ given $k$. Suppose 2 different values of $k$ , say $k_1$ and $k_2$ led to the same of $a$, then it must be the case where $\frac n {k_1} − \frac {k_1+1} {2} = \frac n {k_2} − \frac {k_2+1} {2} \implies \frac n {k_1 k_2} = - \frac 1 2 \implies k_1 k_2 = -2n$. That would require either $k_1$ or $k_2$ to be negative, but since only positive values of $k$ are to be considered, no 2 distinct valid values of $k_1$ and $k_2$ will meet that condition required to yield the same value for $a$. And 2 distinct values of $a$ will result in 2 distinct "untrimmed" sequences, as $a+1$ is the 1st integer in the untrimmed sequences. Since trimming is no done if the original sequnce started at a positive number, 2 distinct positive values of $a$ will continue to be map to 2 distinct sequences.

The other thing to be proven is that even when $a$ is negative, the "trimmed" sequence will be distinct from other valid sequences that sum to $n$.

• If we consider two different negative values of $a$, $a_1$ and $a_2$. As shown earlier, the corresponding "trimmed" sequences should start at $-(a_1 + 1) +1 = -a_1$ and $-(a_2 + 1) +1 = -a_2$ respectively and those should be distinct from each other if $a_1$ and $a_2$ are distinct.
• If we consider a positive value $a_1$ (corresponding to $k = k_1$) and a negative value $a_2$ (corresponding to $k = k_2$) o $a$. The earlier proof already showed that only odd factors of $k$ can yield valid sequences, so any original "untrimmed" sequence must have an odd number of integers. Now trimming is done only when $a$ is negative, and when it is done, an odd number of elements are removed from the sequence (every negative number $-x$ in the original sequence is canceled out by the corresponding positive number $x$, resulting in an even number of positive and negative values getting removed and then number 0 is also removed, so in total an odd number of values get removed). More formally, for the negative value $a_2$, we end up removing $-2(a_1 + 1) +1$ numbers from the sequence, and that count is an odd number. When an odd number of elements are removed from an original sequence containing an odd number, the resulting sequence will have an even number of elements. Thus a sequence that originally started at a negative integer $a_2$ will be trimmed to an even-length sequence, whereas a sequence that originally started as a positive integer $a_1$ will continue to remain an odd-length sequence as it does not get trimmed. Hence the two sequences must be distinct.

 

[fresh_42]

Hence the two sequences must be distinct.

You are not easy to follow. I think you should practice to strip unnecessary explanations in proofs and concentrate more on small logical steps. "should" isn't really appropriate to appear in a proof. Maybe this little article https://www.physicsforums.com/insights/how-most-proofs-are-structured-and-how-to-write-them/ can help, but I'm not sure. I have written better ones than this. So this example here is perhaps a better way to say what I meant:

We still have $2n=(k+1)(2r+k)=2(r+\ldots +(r+k))$ as partition for $n$. The crucial part is to note, that this splits into factors with exactly one of them is odd, hence we can directly compare the factors of:

If we have two decompositions $2n=(k+1)(2r+k)=(l+1)(2s+l)$ and $k+1=l+1$ or $2r+k=2s+l$ are the same odd numbers, then $k=l$ in both cases. If we have $k+1=2s+l$ then $l+1=k+2-2s=\dfrac{2n}{2s+l}=2r+k$ and $r=1-s$ or $r,s\in \{\,0,1\,\}$. For $(r,s)=(0,1)$ we get $2n=(k+1)k=(l+1)(k+1)$ or $k=l+1$, and for $(r,s)=(1,0)$ we have $2n=(l+1)l=l(2+k)$ or $l=k+1$ which is again the same odd factor as $2n=(l+2)(l+1)=(k+1)(k+2)$ is the same decomposition.

 

[archaic]

Spoiler: Speculating on question 15

These are speculations, I can't really answer the question.
$$
S = \int_{\frac{1}{2}}^{3} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx \, + \, \int_{\frac{1}{3}}^{2} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx\\
= \int_{\frac{1}{3}}^{3} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx+\int_{\frac{1}{2}}^{2} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx
$$
This seemed to be equal to zero so I tried computing the area using some triangles and rectangles. I think that it's because of the fact that $\log{\frac{1}{a}}+\log{a}=0$ or something like this.

 

[fresh_42]

Spoiler: Speculating on question 15

These are speculations, I can't really answer the question.
$$
S = \int_{\frac{1}{2}}^{3} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx \, + \, \int_{\frac{1}{3}}^{2} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx\\
= \int_{\frac{1}{3}}^{3} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx+\int_{\frac{1}{2}}^{2} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx
$$
This seemed to be equal to zero so I tried computing the area using some triangles and rectangles. I think that it's because of the fact that $\log{\frac{1}{a}}+\log{a}=0$ or something like this.

So compute $I_n:=\displaystyle{\int_\frac{1}{n}^n} \dfrac{1}{\sqrt{x^2+1}}\,\dfrac{\log(x)}{\sqrt{x}}\,dx$.

 

[odd_even]

Spoiler: Number 15

Sorry, I am new here so I might get some of the formatting wrong.
I first expressed each integral into sums of two integrals:
$$\int_\frac 1 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=\int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_ 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$$$\int_\frac 1 3^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx - \int_ 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$Adding these two equations together:
$$S=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$So, as said before, we need to compute the following integral:
$$I_n=\int_\frac 1 n^n \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$Let $u=\log {x}$:
$$\frac {du} {dx}=\frac 1 x$$$$e^u\,du=dx$$$$I_n=\int_{\log {\frac 1 n}}^{\log n} \frac {e^u} {\sqrt{e^{2u}+1}} {\frac u {\sqrt {e^u}}} \,du=\int_{-\log {n}}^{\log n} \frac {u{\sqrt{e^u}}} {\sqrt{e^{2u}+1}} \,du$$Multiply the numerator and denominator by $\frac {\sqrt{2}} {\sqrt{e^u}}$:$$I_n=\frac 1 {\sqrt{2}} \int_{-\log {n}}^{\log n} u {\sqrt{\frac 2 {e^u+e^{-u}}}} \,du=\frac 1 {\sqrt{2}} \int_{-\log {n}}^{\log n} \frac u {\sqrt{\cosh u}} \,du$$Observe that $\frac u {\sqrt{\cosh u}}$ is an odd function. Therefore: $$I_n=0$$ Finally: $$S=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=0+0=0$$

 

[fresh_42]

Spoiler: Number 15

Sorry, I am new here so I might get some of the formatting wrong.
I first expressed each integral into sums of two integrals:
$$\int_\frac 1 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=\int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_ 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$$$\int_\frac 1 3^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx - \int_ 2^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$Adding these two equations together:
$$S=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$So, as said before, we need to compute the following integral:
$$I_n=\int_\frac 1 n^n \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx$$Let $u=\log {x}$:
$$\frac {du} {dx}=\frac 1 x$$$$e^u\,du=dx$$$$I_n=\int_{\log {\frac 1 n}}^{\log n} \frac {e^u} {\sqrt{e^{2u}+1}} {\frac u {\sqrt {e^u}}} \,du=\int_{-\log {n}}^{\log n} \frac {u{\sqrt{e^u}}} {\sqrt{e^{2u}+1}} \,du$$Multiply the numerator and denominator by $\frac {\sqrt{2}} {\sqrt{e^u}}$:$$I_n=\frac 1 {\sqrt{2}} \int_{-\log {n}}^{\log n} u {\sqrt{\frac 2 {e^u+e^{-u}}}} \,du=\frac 1 {\sqrt{2}} \int_{-\log {n}}^{\log n} \frac u {\sqrt{\cosh u}} \,du$$Observe that $\frac u {\sqrt{\cosh u}}$ is an odd function. Therefore: $$I_n=0$$ Finally: $$S=\int_\frac 1 3^3 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx + \int_\frac 1 2^2 \frac 1 {\sqrt{x^2+1}} {\frac {\log {x}} {\sqrt x}} \,dx=0+0=0$$

Well done! The integration itself can be done a bit easier, but you had all the right ideas. The problem should show, that beside the usual additive symmetry $\int_a^b + \int_b^a =0$ there is sometimes a multiplicative symmetry, too.

If you're interested in more of these, have a look at
https://www.physicsforums.com/threads/solution-manuals-for-the-math-challenges.977057/

 

[benorin]

#8) $\sum_{n=0}^\infty \frac{(-1)^{n}}{\sqrt{n+1}}=\left( 1- \sqrt{2}\right) \zeta (\tfrac{1}{2} )$ hence convergent. But I bet you want the work, so: this a particular value of a Dirichlet series of the the form $\sum \tfrac{a_n}{n^z}$, and for such series there exists an abscissa of convergence $\lambda$ with the property that the series converges whenever $x>\lambda$ and diverges whenever $x<\lambda$-- Knopp, Theory and Application of Infinite Series, pg. 317, #7. Since it is well-known that the series $\zeta(s)= (1-2^{1-s})^{-1}\sum_{n=1}^{\infty}\frac{(-1)^n}{n^s}$ converges for $\Re \left[ s\right] >0$, said abscissa is $\lambda =0$.

In the Cauchy product $\left(\sum_{n=0}^\infty \frac{(-1)^{n}}{\sqrt{n+1}}\right) ^2 =\sum_{j=0}^\infty \sum_{n=0}^j \tfrac{(-1)^{j}}{\sqrt{n+1}\cdot\sqrt{j-n+1}}$ consider the general term of the righthand side (the inner sum) $c_j :=\sum_{n=0}^j \tfrac{(-1)^{j}}{\sqrt{n+1}\cdot\sqrt{j-n+1}}$, by replacing each square root in the denominators with the largest such root, $\sqrt{n+1}$, we see that we must have

$$| c_j |\geq \frac{j+1}{\sqrt{j+1}\cdot\sqrt{j+1}}=1$$

and hence the given Cauchy product is certainly divergent. The reason is that the series we took the Cauchy product of is not absolutely convergent, hence not equal to the square of the sum.

 

[fresh_42]

#8) $\sum_{n=0}^\infty \frac{(-1)^{n}}{\sqrt{n+1}}=\left( 1- \sqrt{2}\right) \zeta (\tfrac{1}{2} )$ hence convergent. But I bet you want the work, so: this a particular value of a Dirichlet series of the the form $\sum \tfrac{a_n}{n^z}$, and for such series there exists an abscissa of convergence $\lambda$ with the property that the series converges whenever $x>\lambda$ and diverges whenever $x<\lambda$-- Knopp, Theory and Application of Infinite Series, pg. 317, #7. Since it is well-known that the series $\zeta(s)= (1-2^{1-s})^{-1}\sum_{n=1}^{\infty}\frac{(-1)^n}{n^s}$ converges for $\Re \left[ s\right] >0$, said abscissa is $\lambda =0$.

In the Cauchy product $\left(\sum_{n=0}^\infty \frac{(-1)^{n}}{\sqrt{n+1}}\right) ^2 =\sum_{j=0}^\infty \sum_{n=0}^j \tfrac{(-1)^{j}}{\sqrt{n+1}\cdot\sqrt{j-n+1}}$ consider the general term of the righthand side (the inner sum) $c_j :=\sum_{n=0}^j \tfrac{(-1)^{j}}{\sqrt{n+1}\cdot\sqrt{j-n+1}}$, by replacing each square root in the denominators with the largest such root, $\sqrt{n+1}$, we see that we must have

$$| c_j |\geq \frac{j+1}{\sqrt{j+1}\cdot\sqrt{j+1}}=1$$

and hence the given Cauchy product is certainly divergent. The reason is that the series we took the Cauchy product of is not absolutely convergent, hence not equal to the square of the sum.

The Leibniz criterion as reason for convergence would have been a lot easier.