Summing over all possibilities.

Probability Level 4

Let n ≥ 3 n \ge 3 be an integer. For an ordered n-tuple of permutation σ \sigma of ( 1 , 2 , ⋯ , n ) (1,2, \cdots ,n) , where σ = ( a 1 , a 2 , ⋯ , a n ) \sigma = \left(a_1, a_2,\cdots, a_n \right) let a function be defined as under

f σ ( x ) = a n x n − 1 + a n − 1 x n − 2 + ⋯ + a 2 x + a 1 f_{\sigma} (x) = a_n x^{n-1} + a_{n-1} x^{n-2} + \cdots + a_2 x + a_1

Let S σ S_{\sigma} denote the sum of solutions to f σ ( x ) = 0 f_{\sigma} (x) = 0 and further denote another sum S S as

S = ∑ over all permutations of σ S σ S = \sum_{\text{over all permutations of } \sigma} S_{\sigma} .

Choose the most appropriate alternative.

Original problem: KVPY 2014 SB/SX

− n ! < S < 0 -n! < S < 0 S > n ! S > n! 0 < S < n ! 0 < S < n! S < − n ! S < -n!

Tapas Mazumdar by Tapas Mazumdar , 20, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Oct 24, 2017

Since f σ = − a n − 1 a n f_\sigma = -\frac{a_{n-1}}{a_n} , we see that S = − ∑ σ a n − 1 a n = − ∑ u ≠ v u v ( n − 2 ) ! = − ( n − 2 ) ! ( ∑ u , v = 1 n u v − n ) = − ( n − 2 ) ! [ 1 2 n ( n + 1 ) H n − n ] = − n × ( n − 2 ) ! [ 1 2 ( n + 1 ) H n − 1 ] \begin{aligned} S & = \; -\sum_\sigma \frac{a_{n-1}}{a_n} \; = \; -\sum_{u \neq v} \frac{u}{v}(n-2)! \; = \; -(n-2)! \left(\sum_{u,v=1}^n \frac{u}{v} - n\right) \\ & = \; -(n-2)! \big[\tfrac12n(n+1)H_n - n\big] \; =\; -n\times(n-2)! \big[\tfrac12(n+1)H_n - 1\big] \end{aligned} Note that 2 H 3 − 1 = 8 3 > 2 2H_3 - 1 = \tfrac83 > 2 . Moreover, since H 4 = 25 12 H_4 = \tfrac{25}{12} we see that 1 2 ( n + 1 ) H n − 1 ≥ 25 24 ( n + 1 ) − 1 > n − 1 \tfrac12(n+1)H_n - 1 \ge \tfrac{25}{24}(n+1) - 1 > n - 1 for all n ≥ 4 n \ge 4 , and so we see that S < − n ! S < -n! for n ≥ 3 n \ge 3 .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

I wasn't able to solve the problem myself so I published the problem hoping I get a solution. Thanks for uploading the solution.

However, I was left behind at this part

∑ u , v = 1 n u v = 1 2 n ( n + 1 ) H n \sum_{u,v=1}^n \dfrac uv = \dfrac 12 n(n+1) H_n

Can you please explain it to me? I know the definition of harmonic number but couldn't connect the dots here.

Tapas Mazumdar - 3 years, 7 months ago

Log in to reply

The LHS simply factorises as ( ∑ u u ) ( ∑ v v − 1 ) \left(\sum_u u\right)\left(\sum_v v^{-1}\right)

Mark Hennings - 3 years, 7 months ago

Log in to reply

Thanks, I see it now. :)

Tapas Mazumdar - 3 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...