# Find a closed expression for a formula including summation

Let:
$$\sum\limits_{k = 0}^n {k\left( {\matrix{ n \cr k \cr } } \right)} \cdot {4^{k - 1}} \cdot {3^{n - k}}$$

Find a closed formula (without summation). I think I should define this as a "series" which generated by $F(x)$. I don't really have a lead here.

Any ideas? Thanks.

• it looks like the derivative of $(x+3)^n$ at $x=4$. – fernanfio Jun 17 '14 at 18:06

According to the binomial theorem, we have $$(x+y)^n=\sum_{k=0}^n\binom{n}{k} x^k y^{n-k}.\tag1$$ Differentiating $(1)$ with respect to $x$ yields $$n(x+y)^{n-1}=\sum_{k=0}^n \binom{n}{k} k\ x^{k-1} y^{n-k},\tag2$$ then pluging in $x=4$ and $y=3$ to $(2)$.

• Great approach! – AnnieOK Jun 17 '14 at 18:08
• Generally, In discrete mathematics course, In all such identities which can be solved by $k\binom{n}{k}=n\binom{n-1}{k-1}$, I used differentiation or integration :) – Fardad Pouran Jun 17 '14 at 18:17

Hint: Use the fact that for $k\ge 1$ we have $k\binom{n}{k}=n\binom{n-1}{k-1}$ and think Binomial Theorem.

Hint: $$\sum\limits_{k = 0}^n {\left( {\matrix{ n \cr k \cr } } \right)} \cdot {x^{k}} \cdot {3^{n - k}}=\left(x+3\right)^n$$

The binomial expansion is given by \begin{align} (1+x)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k}. \end{align} Differentiating both sides with respect to $x$ yields \begin{align} n (1+x)^{n-1} = \sum_{k=0}^{n} k \ \binom{n}{k} x^{k-1}. \end{align} Multiplying this last expression by $3^{n} 4^{-1}$ leads to \begin{align} \frac{3^{n} n}{4} \ x(1+x)^{n-1} = \sum_{k=0}^{n} k \ \binom{n}{k} 4^{-1} 3^{n} x^{k}. \end{align} Now let $x = 4/3$ to obtain the desired expression \begin{align} n \cdot 7^{n-1} = \sum_{k=0}^{n} k \ \binom{n}{k} 4^{k-1} 3^{n-k}. \end{align}

As a Hint : \begin{align*} \sum_{k = 0}^n k\binom{n}{k}4^{k-1}\cdot3^{n-k}=0\cdot\binom{n}{0}\cdot4^{-1}\cdot3^n+\sum_{k = 1}^n n\binom{n-1}{k-1}4^{k-1}\cdot 3^{n-k} \end{align*}

• I tried to progress from here but you have to handle negative binomial. How to fix this technical issue? Thanks. – AnnieOK Jun 17 '14 at 18:27
• Ah OK.. still no problem ... you can separate the term $k=0$ from summation and rewrite summation starting from $k=1$. I'll edit my post – Fardad Pouran Jun 18 '14 at 4:29