# Did I do this convolution problem correct?

Work attached

#### Attachments

• 347.1 KB Views: 15
• 314.1 KB Views: 13

#### romsek

MHF Helper

This is a tricky problem. It needs care and neatness.

Don't forget both distribution sequences are finite.

#### romsek

MHF Helper
I'm seeing that

$c(n) = \begin{cases} \sum \limits_{k=0}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&0\leq n \leq M\\ \sum \limits_{k=n-M}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&M+1 \leq n \leq N+M \end{cases}$

we can clean that up a bit

$c(n) = p^n (1-p)^{N+M-n}\sum \limits_{k=\ell}^n \dbinom{N}{k}\dbinom{M}{n-k}$

where $\ell = \begin{cases}0 &0\leq n \leq M\\n-M &M+1\leq n \leq N+M\end{cases}$

#### romsek

MHF Helper
$c(n) = p^n (1-p)^{N+M-n}\sum \limits_{k=\ell}^n \dbinom{N}{k}\dbinom{M}{n-k}$

where $\ell = \begin{cases}0 &0\leq n \leq M\\n-M &M+1\leq n \leq N+M\end{cases}$
Ideally we'd like to show that the sum is equal to $\dbinom{N+M}{n}$.

I confess I haven't been able to do that.

Would this work?

romsek

#### romsek

MHF Helper
Would this work?

why yes I believe it would!

#### math951

why is M+1 < n < M+N
Where do we get this boundary? I follow everything else.

#### math951

I guess also, o<n<M as well.

So basically, you are telling me that, If n is between 0 and or equal to M, then we get 0.... why?

#### romsek

MHF Helper
I guess also, o<n<M as well.

So basically, you are telling me that, If n is between 0 and or equal to M, then we get 0.... why?
no.. where do you get that from?

The sum has to be treated differently for the cases $0 \leq n \leq M$ and $M+1 \leq n \leq M+N$

You have two sequences that you are basically dotting one another with. One is stationary, the other is flipped in index and slid one step at a time to the right.
For $0 \leq n \leq M$ the flipped sequence is $0$ for $k > n$. At $n = M$ the entire flipped sequence now does intersect with the entire stationary sequence.

Then at $n=M+1$ the flipped sequence starts being $0$ at the beginning of the sum. It only has $M$ non-zero values.

I see I've got a mistake in the formula. The stationary sequence values are zero for $k > N$ so the sum should be

$c(n) = \begin{cases} \sum \limits_{k=0}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&0\leq n \leq M\\ \sum \limits_{k=n-M}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&M+1 \leq n \leq N\\ \sum \limits_{k=n-M}^N \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&N+1 \leq n \leq M+N \end{cases}$

Let me see if I can gen up some pictures for you.

#### romsek

MHF Helper
Ok, 4 regions of interest. The first picture is $n=0$ to get you oriented.

The sliding sequence, red, is reversed with it's last element occurring at 0. The stationary sequence, blue, starts at 0.

Next we have $n=5$ We start the sum at 0, and we end it at $n$ This is because the stationary sequence is 0 prior to 0
and the sliding sequence is 0 after $n$

Next we have $n=15$ where the end of the sliding sequence is now past 0.

We sum from $n-M$ to $n$ as the sliding sequence is 0 prior to and after these indices.

Finally we have $n=21$ where the leading part of the sliding sequence has slid past the end of the stationary sequence.

Here we sum from $n-M$ to $N$ because the stationary sequence is 0 after that.

I don't suppose you have Mathematica do you?

math951