0

Is it possible to simplify the following expression, where $k$ is a given constant? I want to simplify it to something in terms of only $k$.

$ \sum_{i=0}^{\lfloor \frac{k}{2} \rfloor} 2^{k} \binom{k-i}{i}$. I was confused on how to deal with the $i$ in the combination.

amWhy
  • 209,954
Laura
  • 25
  • 4
  • 1
    Why is $2^k$ even in this? And why the linear algebra tag? – Ted Shifrin Mar 30 '24 at 19:18
  • 2
    Moving the $2^k$ out, the rest is the k-th Fibonacci number, shifted. so for k=0,1,2,3,4... it is 1,1,2,3,5... I think this is known way to get Fibonaccis via adding Pascal triangle on slant. – coffeemath Mar 30 '24 at 19:34
  • @TedShifrin Sorry, the $2^{k}$ was in the original problem and I forgot to factor it out before asking. Also could you let me know what would be a better tag to use next time? – Laura Mar 30 '24 at 19:42
  • Sure. Combinatorics is appropriate, as is combinations. – Ted Shifrin Mar 30 '24 at 19:45
  • @coffeemath This should be an answer. Proof by induction? The moral of the story is: Write out plenty of examples and look at patterns. – Ted Shifrin Mar 30 '24 at 19:47
  • @TedShifrin I only calculated ten terms and noticed a pattern, which I then only conjectured was the "slanted Pascal triangle" fact I knew about. Hence I just commented. – coffeemath Mar 30 '24 at 23:39

1 Answers1

0

I'm not sure if you meant to wrote $2^i$ instead of $2^k$, because otherwise you can just take the $2^k$ out of the summation.

For the latter case, we have $$\sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}2^k\begin{pmatrix}k-i\\i\end{pmatrix} = 2^k\cdot\sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}\begin{pmatrix}k-i\\i\end{pmatrix}$$ Let $a_k$ denote the summation on the right hand side, then we have \begin{align*} a_k &= \sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}\begin{pmatrix}k-i\\i\end{pmatrix} = \sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}(\begin{pmatrix}k-i-1\\i-1\end{pmatrix}+\begin{pmatrix}k-i-1\\i\end{pmatrix})\\ &= \sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}\begin{pmatrix}k-i-1\\i-1\end{pmatrix} + \sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor}\begin{pmatrix}k-i-1\\i\end{pmatrix}\\ &= \sum\limits_{i=0}^{\lfloor\frac{k}{2}\rfloor-1}\begin{pmatrix}k-2-i\\i\end{pmatrix} + \sum\limits_{i=0}^{\lfloor\frac{k-1}{2}\rfloor}\begin{pmatrix}k-1-i\\i\end{pmatrix}\\ &= a_{k-2}+a_{k-1} \end{align*} Also we can compute that $a_0=a_1=1$, so $a_k$ equals the $k$-th Fibonacci number, and the answer is $2^k\cdot F_k$ where $F_k$ denotes the $k$-th Fibonacci number.

If it's the former case, call the whole summation $b_k$, then you should arrive a recursion $b_k = b_{k-1} + 2b_{k-2}$ by similar means. The sequence is given by https://oeis.org/A001045.

By the way, you might want to pay more attention to your tags, since I can't think of any possible way of this problem relating to linear algebra.

Ayden Chang
  • 11