CODIGO 2k20, Weird Function Help

problem link - https://www.codechef.com/COG2020/problems/COG2007
I am not able to simplify the expression in the problem. can anyone help?

1 Like

\sum_0^n\binom{n}{i}=2^n
and
(a+b)^n = \sum_0^n \binom{n}{i}a^ib^{n-i}
so when m=1
\sum_0^n\sum_0^{n-i}\binom{n}{i}\binom{n-i}{j}
=\sum_0^n \binom{n}{i} \times \sum_0^{n-i}\binom{n-i}{j}
since \binom{n}{i} is independent of j.
=\sum_0^n \binom{n}{i} \times 2^{n-i}
=(1+2)^n = 3^n
now when m=2
f(n,2)=\sum_i^n \binom{n}{i}f(n-i,1)
=\sum_i^n \binom{n}{i}3^{n-i}
=(3+1)^n = 4^n
by recursion, f(n,m)=(m+2)^n
\prod_{1}^{n} f(i,m)
=\prod_{1}^{n} (m+2)^i
=(m+2)^{\sum_0^n i}
=(m+2)^\frac{n*(n+1)}{2}

7 Likes

Thanks a lot!

nice thanks a alot