Could we further simplify this:
$ \sum_{i=1}^{k}{{k \choose i} \cdot 12^i \cdot 2^i}$
or, at least, find a close upper bound?
Could we further simplify this:
$ \sum_{i=1}^{k}{{k \choose i} \cdot 12^i \cdot 2^i}$
or, at least, find a close upper bound?
Firstly, note that $12^i * 2^i$ is nothing more than $24^i$.
So consider $1 + \displaystyle\sum_{i=1}^{k}{{k \choose i} \times 12^i \times 2^i} = \displaystyle\sum_{i=0}^{k}{{k \choose i} \times 24^i} = (1 + 24)^k$. (by the binomial theorem).
So your sum is nothing more than $25^k - 1$.
Hint: lookup Binomial theorem.
$(1+24)^k=\sum\limits_{i = 0}^k {{k \choose i}24^i }$.