Using Mathematica to derive analytic form of single variable function

Question

I am interested in finding an analytical form of the following function $f(n)$ defined as: $$f(n):=\sum_{\{\bar{K}\}}\prod_{l<j}^{n}e^{ik_lk_j},$$ where $\{\bar{K}\}$ is the full set of binary permutations of length $n$ and $i$ denotes complex $i$. Example for $n = 3$ we get $$\{\bar{K}\} = \{\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 0\}, \{1, 0, 0\}, \{0, 1, 1\}, \{1, 0, 1\}, \{1, 1, 0\}, \{1, 1, 1\}\}.$$ Can Mathematica assist in deriving a function in terms of $n$ in a purely mathematical form? The following code defines and evaluates the function $f$ for a given $n$:

n = 3;

K[n_] := Flatten[GatherBy[Tuples[{0, 1}, n], Total], 1]
P[n_, k_] := 
  Product[If[i < j, Exp[I*K[n][[k]][[i]]*K[n][[k]][[j]]], 1], {i, 1, 
    n}, {j, 1, n}];

f[n_] := Sum[P[n, k], {k, 1, 2^n}]
f[n]
f[x]

It gives the correct result for chosen $n$, but not a clean analytical form in terms of variable $n$, which I am looking for (the result at the end as you can see is still somewhat in numerical form).

As JimB correctly showed in his answer, the analytic form can be found by identifying a pattern. But in this case I am particularly interested in a more direct approach using Mathematica's symbolic tools. I'm particularly interested in a direct symbolic way of coding the summation $\sum_{\overline{K}}(\cdot)$, this is the tricky part.

Any ideas on how to make the most of Mathematica to assist in this task? Thanks.

Answer 1

If one makes a table of the first few values of $n$, then a pattern becomes evident:

Table[{n, f[n]}, {n, 3, 8}] // TableForm

One can see that the leading term is $n+1$. The other coefficients associated with the $e^{z i}$ are just binomial coefficients (which also could be determined by typing in 28,56,70,56,28,8,1 at oeis.org):

n = 8;
Table[Binomial[n, k], {k, 2, n}]
(* {28, 56, 70, 56, 28, 8, 1} *)

The exponents are found with

n = 8;
Table[k (k - 1)/2, {k, 2, n}]
(* {1, 3, 6, 10, 15, 21, 28} *)

Putting these two sequences together we have

Sum[E^(I k (k - 1 )/2)*Binomial[n, k], {k, 0, n}]

or

$$\sum _{k=0}^n \binom{n}{k} e^{\frac{1}{2} i k (k-1)}$$

Addition

The OP has more than reasonably asked for a solution that really involves Mathematica functionality. I still don't know how to do that. But here is an alternative to searching for patterns (as done above).

The function P[n,k] can be rewritten as

P[n_, k_] := Exp[I Sum[K[n][[k]][[i]]*K[n][[k]][[j]], {j, 2, n}, {i, 1, j - 1}]]

Note that the sum

Sum[K[n][[k]][[i]]*K[n][[k]][[j]], {j, 2, n}, {i, 1, j - 1}]

is the number of ways to choose 2 1's from the $k$-th arrangement (as the product K[n][[k]][[i]]*K[n][[k]][[j]] will only be 1 if both terms are 1 and 0 otherwise. If there are $x$ 1's in the $k$-th arrangement, then the number of ways to choose 2 1's is $x(x-1)/2$.

Also, there are ${n}\choose{x}$ arrangements with $x$ 1's with $x=0,1,\ldots,n$. So the general formula will be

$$\sum_{x=0}^n {{n}\choose{x}} e^{i x(x-1)/2}$$