How to solve $1+\sum_{k=1}^r 3^k\binom{n}{k}$ (using, say, $ S\{n\} = \frac{a_1(1-r^n)}{1-r} $) so I can use it for large $r$?

Question

Following the solution to my previous post in: Counting unique element output from a product of combination

where the number of unique string-variants generated from a given string is:

$$ 1+\sum_{k=1}^r 3^k\binom{n}{k} $$

How to solve the summation so that I could use this formula for large $r$?

My attempt: I try to solve it using a general formula: $$ S\{n\} = \frac{a_1(1-r^n)}{1-r} $$ for $a = 3$ and the common factor $r = 3$. But it turns out that is wrong since the formula above did not has anything to do with the binomial coefficient. Anyone can help?

Answer 1

This sum does not have an elementary representation. Let $f(r,n)$ be your sum. By a CAS \begin{align*} f(r,n) &= 1 + \sum_{k=1}^r 3^k \binom{n}{k} \\ &= 4^n - 3^{r+1}\binom{n}{r+1}{}_2F_1(1,r-n+1;r+2;-3) \end{align*}

where ${}_2F_1$ is the Gaussian hypergeometric function. Even assuming $r$ and $n$ integers with $0 < r < n$, there are no simplifications to elementary functions.

For $1 \leq r < n$, use the sum. This is easy as long as $n$ is not large. You give no hints about the size of $n$ in your question. Your prior post claims you are only interested in $1 \leq r \leq 4$, so this sum is nearly immediate.

For $r \geq n$, $f(r,n) = 4^n$. This follows from your sum since $\binom{n}{n+1} = \binom{n}{n+2} = \cdots = 0$, so the sum cuts itself off after $r = n$, and a standard identity (first one at that link, taking $x = 3$ and realizing the $k = 0$ term is the "$1+$" in $f$). In the context of your previous post (not having read it in detail) -- once you've decided to replace every character in your string, then you have any $n$-length string you want from your 4 character alphabet, giving $4^n$ possibilities.

---

Digging through OP's referenced Question, he most likely intends $1 \leq r \leq 4$ and $r \leq n$. These constraints appear nowhere in the current Question. With those constraints ... \begin{align*} f(1,n) &= 1 + 3n \text{,} \\ f(2,n) &= 1 + 3n + \frac{9}{2}n(n-1) \text{,} \\ f(3,n) &= \frac{1}{2}(9n^2 -3n+2) + \frac{9}{2}n(n-1)(n-2) \text{, and} \\ f(4,n) &= \frac{1}{2}(9n^3 - 18 n^2 + 15 n + 2) + \frac{27}{8}n(n-1)(n-2)(n-3) \text{.} \end{align*}

For example, $f(4,10\,000) = 33\,734\,252\,812\,372\,501$. I note this because representing such quantities in a programming language as precise integers (instead of imprecise floating point approximations) can require some effort. Letting $r$ and $n$ be "large" necessitates this effort. If you intend to generate these numbers in a programming language, it would help to know which language you are targetting.

---

Just testing for timing, I get the complete set of results for $n = 10\,000$ in about 180 ms using this code:

import itertools
import time

class sumterm:
    """Iterator to produce terms of a specific sum counting replaced strings."""
    def __init__(self, nInit):
        # Rememember: Iterators start in a "prior to the first element" state 
        # and are expected to yield the first element on the first call to 
        # __next__().
        self.n = nInit
        self.k = 0
        self.term = 1  # 3^k binom(n,k) = 1 binom(n,0) = 1, when k = 0

    def __iter__(self):
        try: self.n
        except NameError: raise ValueError("sumterm objects must be initialized before iterating.")

        return self

    def __next__(self):
        if self.k < self.n:
            # 3^(k+1) binom(n,k+1) = 3^k binom(n,k) * 3(n-k)/(k+1)
            # Integer division ( // ) is safe because divisibility is ensured.
            self.term = self.term * 3*(self.n - self.k) // (self.k+1)
            self.k += 1
            return self.term
        else:
            raise StopIteration

n = 10000
tBefore = time.time()
terms = list(iter(sumterm(n)))
partialSums = [1+x for x in itertools.accumulate(terms) ]
tAfter = time.time()

print("For n = ", n, ", k = 1 .. 11: ",  partialSums[:11])
print("Took",  tAfter - tBefore,  " seconds.")

Don't bother trying to print the last few terms. $4^{10\,000}$ is too large to usefully look at.

Note that partialSums[k-1] is $f(k,n)$ for $k \leq n$.

---

\begin{align*} f(1,n) &= 1 + \sum_{k=1}^1 3^k \binom{n}{k} \\ &= 1 + 3^1 \binom{n}{1} \\ &= 1 + 3 n \text{, } \\ f(2,n) &= 1 + \sum_{k=1}^2 3^k \binom{n}{k} \\ &= 1 + 3^1 \binom{n}{1} + 3^2 \binom{n}{2} \\ &= 1 + 3 n + 9\frac{n(n-1)}{2} \text{, } \\ f(3,n) &= 1 + \sum_{k=1}^3 3^k \binom{n}{k} \\ &= 1 + 3^1 \binom{n}{1} + 3^2 \binom{n}{2} + 3^3 \binom{n}{3} \\ &= 1 + 3 n + 9\frac{n(n-1)}{2} + 27\frac{n(n-1)(n-2)}{6} \\ &= \frac{1}{2}(2 + 6n + 9n(n-1)) + \frac{9}{2}n(n-1)(n-2) \\ &= \frac{1}{2}(9n^2 - 3 n + 2) + \frac{9}{2}n(n-1)(n-2) \text{,} \end{align*} and \begin{align*} f(4,n) &= 1 + \sum_{k=1}^4 3^k \binom{n}{k} \\ &= 1 + 3^1 \binom{n}{1} + 3^2 \binom{n}{2} + 3^3 \binom{n}{3} + 3^4 \binom{n}{4} \\ &= 1 + 3 n + 9\frac{n(n-1)}{2} + 27\frac{n(n-1)(n-2)}{6} + 81\frac{n(n-1)(n-2)(n-3)}{24} \\ &= \frac{1}{2}(2 + 6n + 9n(n-1) + 9n(n-1)(n-2)) + \frac{27}{8}n(n-1)(n-2)(n-3) \\ &= \frac{1}{2}(9 n^3 - 18 n^2 + 15 n + 2) + \frac{27}{8}n(n-1)(n-2)(n-3) \text{.} \\ \end{align*}

Answer 2

In case you are interested in asymptotics:

$$\begin{align} s(n,r)&=\sum_{k=1}^r 3^k\binom{n}{k}\\ &=2^n\sum_{k=1}^r 3^k\frac{\binom{n}{k}}{2^n}\\ &\approx \frac{2^n}{\sqrt{\pi n /2}} \int_0^r 3^x \exp\left( -\frac{2}{n}(x-n/2)^2 \right) dx \\ \end{align}$$

If $r > 0.78 n$ we can apply Laplace's method and get the first order approximation:

$$ \frac{\log (s(n,r))}{n} \to \log(2) + \frac{\log^2(3)+ 4 \log 3}{8}\approx 1.393$$

For smaller $r$ , a similar approximation can be obtained (tell me if you are interested) but it involves both $(n,r)$ variables.