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

Answer:

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

Step-by-step 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$