# Finding linear convolution of two time series

PROBLEM

Two real, causal time series

$$f_k = a^k \quad \text{and} \quad g_k = b^k$$

where $a \neq b$, $|a| < 1$, and $|b| < 1$, are given for $k = 0,1,2,...$

Find the linear convolution $h_n$ of the time series $f_k$ and $g_k$.

ATTEMPTED SOLUTION

I think perhaps my attempted solution here can be improved upon. We have from the definition:

$$h_n = \sum_{k=0}^{n} f_k g_{n-k} = \sum_{k=0}^{n} a^k b^{n-k} = b^n \sum_{k=0}^{n} \left(\frac{a}{b} \right)^k$$

If we let $R = \left(\frac{a}{b} \right)$, the last term can be written as:

$$h_n = b^n \cdot \frac{1 - R^{n+1}}{1 - R}$$

or

$$h_n = \frac{b^n - \frac{a^{n+1}}{b}}{1 - \frac{a}{b}}$$

$$h_n = \frac{b^{n+1} - a^{n+1}}{b-a}$$

I don't see how I can improve upon this answer though, but since we are given certain conditions in the problem, I have a feeling that it is possible to get a more elegant solution. I see that as $n \to \infty$, $h_n \to 0$, but is there any way I can "improve" on the answer for any $n$?

• Your answer is perfectly correct and there is no "simpler" answer. If you divide out the $b-a$ in the denominator into the numerator, you just get $$h_n = b^n + ab^{n-1}+a^2b^{n-2}+ \cdots + ba^{n-1}+a^n$$ which, if you think about it a bit, is right where you started from in $\displaystyle \sum_{k=0}^{n} a^k b^{n-k}$. – Dilip Sarwate May 21 '14 at 21:59
• @DilipSarwate: I don't see any better answer than your comment; you might as well convert it to one. – Jason R May 22 '14 at 1:25
• Thanks a lot, everybody! I really appreciate your input. – Kristian May 22 '14 at 7:58

There is a small mistake in your solution. Here $f_k$ and $g_k$ are infinite duration signal, ie. $n \to \infty$. You made a mistake that you took n in $h_n$ and number of coefficients in $f_k$ or $g_k$ as same, but it is different.

$$h_n = \sum_{k=0}^{\infty} f_k g_{n-k} = \sum_{k=0}^{\infty} a^k b^{n-k} = b^n \sum_{k=0}^{\infty} \left(\frac{a}{b} \right)^k$$

$$h_n = b^n \cdot \frac{1}{1 - \frac{a}{b}}$$

$$h_n = \frac{b^{n+1}}{b-a}$$

If you want to finite the number of coefficients in $f_k$ and $g_k$, use other variables other than n.

Then n in the RHS of your equation will replace with the new variable.

• Errr no. It is your calculation that contains a big mistake; the OP's analysis is quite correct. Your mistake is in your second equality. It is true that $h_n = \sum_{k=0}\infty f_f g_{n-k}$ but for any given nonnegative value of $n$, say $n = 5$ for example, the sum is \begin{align}h_5&=f_0g_5+f_1g_4+f_2g_3+f_3g_2+f_4g_1+f_5g_0+f_6g_{-1}+f_7g_{-2}+\cdots\\&=f_0g_5+f_1g_4+f_2g_3+f_3g_2+f_4g_1+f_5g_0\end{align} since $g_{-1}=g_{-2}=g_{-3}=\cdots = 0$. You have assumed that $g_i=b^i$ for all $i$ which is not correct: $g_i = 0$ for $i < 0$. – Dilip Sarwate May 22 '14 at 2:22