For two sequences of complex numbers $\{a_0, a_1, ..., a_n, ...\}$ and $\{b_0, b_1, ..., b_n, ...\}.$ Show that the following relations are equivalent: \begin{equation} a_n = \sum_{k=0}^n b_k \iff b_n = \sum_{k=0}^n(-1)^{k+n}a_k \text{ for all } n. \end{equation}

I know it had to do with some type of Mobius inversion. I tried as follows

\begin{align} \sum_{k=0}^n b_k &= \sum_{k=0}^n \sum_{m=0}^k(-1)^{m+k}a_m \\ &= \sum_{m=0}^n \sum_{k=m}^n(-1)^{m+k}a_m \\ &= \sum_{m=0}^n(-1)^ma_m \sum_{k=m}^n(-1)^{k} \end{align}

I have no idea what to do next. I am not even sure that I interchange sum in correct way. Any help will be really appreciated. Thanks.

Note--I saw similar questions but they are not of so much help.

  • 1
    $\begingroup$ There seems to be a mistake? Let $a_n=n+1$ and $b_n=1$. Then $a_n=\sum_{k=0}^n b_k$, but $1\neq \sum_{k=0}^n (-1)^{k+n}(k+1)$. $\endgroup$ – Mike Earnest Feb 22 at 19:30
  • $\begingroup$ @MikeEarnest Well this is a problem form Berkeley. The problem 10 on Page 7 of math.berkeley.edu/~stankova/MathCircle/Multiplicative.pdf $\endgroup$ – Learner Feb 22 at 19:42
  • $\begingroup$ Your source is wrong, then. Obviously, $a_n=\sum_{k=0}^nb_k$ if and only if $b_n=a_n-a_{n-1}$ (except $b_0=a_0$), and in general $a_n-a_{n-1}\neq a_n-a_{n-1}+a_{n-2}-a_{n-3}+\dots+(-1)^n a_0$. $\endgroup$ – Mike Earnest Feb 22 at 19:51

I agree the question is not correct as stated. However, I believe it's a typo on the starting value of the first sum, with it meant to be for $k = n - 1$, as this will then make the question correct. Thus, the statement to prove would instead be

$$a_n = \sum_{k=n-1}^n b_k \iff b_n = \sum_{k=0}^n(-1)^{k+n}a_k \text{ for all } n \tag{1}\label{eq1}$$

This can be shown using induction. First, note that $n = 0$, where the sum starts at $0$, we get $a_0 = b_0$ on the left & right sides. For $n = 1$, the left side gives $a_1 = b_0 + b_1$, from which $b_1 = -b_0 + a_1 = -a_0 + a_1$, which is the right side.

Next, assume this holds true for all $n \le m$ for some integer $m \ge 0$. For $n = m + 1$, the left side of \eqref{eq1} becomes

$$a_{m+1} = b_{m} + b_{m+1} \Rightarrow b_{m+1} = -b_{m} + a_{m+1} \tag{2}\label{eq2}$$

From the induction hypothesis, we get that

\begin{align} -b_{m} & = -\sum_{k=0}^m (-1)^{k+m}a_k \\ & = \sum_{k=0}^m (-1)^{k+\left(m + 1\right)}a_k \\ & = \sum_{k=0}^{m+1} (-1)^{k+\left(m + 1\right)}a_k - \left(-1\right)^{\left(m+1\right)+\left(m+1\right)}a_{m+1} \\ & = \sum_{k=0}^{m+1} (-1)^{k+\left(m + 1\right)}a_k - a_{m+1} \end{align}

Substituting this into \eqref{eq2} gives that

$$b_{m+1} = \sum_{k=0}^{m+1} (-1)^{k+\left(m + 1\right)}a_k \tag{3}\label{eq3}$$

This proves the statement one way. As all of the steps are reversible, this means the statement is also true the other way. Thus, it's also true for $n = m + 1$, completing the induction procedure.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.