Prove an existing formula for a limit of a specific sum Prove that$$\lim_{n\to\infty}\frac1n\sum_{i_1,i_2,...i_k=1}^n\lambda_1^{|i_1-i_2-s_1|}\lambda_2^{|i_2-i_3-s_2|}...\lambda_k^{|i_k-i_1-s_k|}$$is equal to$$\sum_{j=1}^k\lambda_j^{S+k-1}\prod_{l=1,l\ne j}^k\frac{1-\lambda_l^2}{(\lambda_j-\lambda_l)(1-\lambda_j\lambda_l)}$$where all $\lambda$s are, in absolute value, smaller than 1, distinct from one another, and $S=|s_1+s_2+...+s_k|$. This can be done by 'brute force' for $k=2$, $k=3$ and $k=4$ but I have no idea how to continue; yet I am reasonably confident that the formula is correct for any $k$.
 A: Denote $$A=\sum_{p_1+\ldots+p_k=S} \lambda_1^{|p_1|}\lambda_2^{|p_2|}\ldots
\lambda_k^{|p_k|}.\quad (1)$$
We prove two things:
1) Your limit equals $A$. 
2) $A$ equals to what you write.
Start with 1). Note that any summand in your expression is of the form $\lambda_1^{|p_1|}\lambda_2^{|p_2|}\ldots
\lambda_k^{|p_k|}$ for $\sum p_i=S$ (if $S$ is positive, define $p_m=i_{m+1}+s_m-i_m$, otherwise $p_m=i_m-i_{m+1}-s_m$ for $m=1,\ldots,k$, indices are cyclic), and each term appears at most $n$ times, since for fixed $i_1$ it appears at most once. Thus 
$$
\frac1n\sum_{i_1,i_2,...i_k=1}^n\lambda_1^{|i_1-i_2-s_1|}\lambda_2^{|i_2-i_3-s_2|}...\lambda_k^{|i_k-i_1-s_k|}\leqslant A,
$$
and the upper limit does not exceed $A$. On the other hand, for any $B<A$ we may find finitely many terms in the sum (1) whose sum exceeds $B$. Each of this terms appears in your sum $n-O(1)$ times, thus we get that the lower limit is at least $B$. Since $B<A$ was arbitrary, it implies that the limit exists and equals to $A$.
2) $A$ is the coefficient of $t^S$ in the Laurent series
$F:=\prod_i \sum_{p\in \mathbb{Z}} t^p \lambda_i^{|p|}$ (which is defined for $|t|$ close enough to 1), $i$-th multiple equals $1/(1-t\lambda_i)+\lambda_i/(t-\lambda_i)=t(1-\lambda_i^2)/((1-t\lambda_i)(t-\lambda_i))$. The product of these guys is a rational function in $t$ which is a linear combinations of the functions $1/(1-\lambda_jt)$ and $1/(\lambda_j-t)$:
$$
F=\sum_j C_j/(1-\lambda_jt)+D_j/(\lambda_j-t).\quad (2)
$$
$D_j/(\lambda_j-t)$ does not provide a coefficient of $t^S$ (it is expressed via negative powers of $t$), the coefficient of $t^S$ may come from $1/(1-\lambda_jt)=\sum_{n=0}^\infty \lambda_j^n t^n$. It remains to calculate the coefficient $C_j$ in the decomposition (2). We have $C_j=(F(t)(1-\lambda_jt))_{t=1/\lambda_j}$ that gives your formula.
