Question

Define g(n):=f(n!). We want to find a closed formula for g(n)g(n). First of all, we want to find a recurrence for g(n)g(n). If nn is odd, then it is pretty easy to see that g(n) = g(n-1)g(n)=g(n−1). If nn is even, try to write g(n)g(n) in terms of g(n/2)g(n/2).

Answer 1

`g(n)=g(n/2)+n/2`

Explanation:

`(2k+1)!=1*3*5*7*...*(2k-1)*(2k+1)*2*4*6*8*...*(2k-2)*(2k)`

Notice that the odd factors of above equality don't contribute to the largest power of 2 that divides (2k+1)!

Therefore, we can conclude that
`g(2n+1)=g(2n)`.

`(2k)!=1*3*5*7*...*(2k-3)*(2k-1)*2*4*6*8*...*(2k-2)*(2k)=\\= (1*3*5*...*(2k-3)*(2k-1))*((2*1)*(2*2)*(2*3)*...*(2*(k-1))*(2*k))=\\= (1*3*5*...*(2k-3)*(2k-1))*2^k*k!`

Notice that the odd factors of above equality don't contribute to the largest power of 2 that divides (2k)!

Hence,
`g(2k)-g(k)=k`

So for
`k = n/2`,

`g(n)-g(n/2)=n/2\\g(n)=g(n/2)+n/2`