# PROVE BY INDUCTION

• Dec 10th 2008, 04:48 AM
poppy12345
PROVE BY INDUCTION
I have a question and am unsure how to start it:

Prove by induction that
(sum from k=1 to n)of
k(k+1)...(k+a) = 1/(a+2)*n(n+1)(n+2)....(n+a+1)
• Dec 10th 2008, 07:19 AM
Proof by induction
Hello -

Quote:

Originally Posted by poppy12345
I have a question and am unsure how to start it:

Prove by induction that
(sum from k=1 to n)of
k(k+1)...(k+a) = 1/(a+2)*n(n+1)(n+2)....(n+a+1)

Tricky to know where to start, isn't it? Is it $\displaystyle n$ that we vary, or $\displaystyle a$?

Well, start in the usual way, by writing a proposition about $\displaystyle n$, and let $\displaystyle a$ take care of itself. So:

Let $\displaystyle S_n = \sum_{k=1}^n k(k+1)...(k+a)$

Then the propositional function $\displaystyle P(n)$ is defined as:

$\displaystyle P(n)\equiv S_n = \frac{1}{a+2}n(n+1)(n+2)...(n+a+1)$

Then write down the sum $\displaystyle S_{n+1}$ as $\displaystyle S_n +$ the term you get when $\displaystyle k=(n+1)$.

You'll find you can then take out lots of common factors, and eventually express this as $\displaystyle \sum_{k=1}^{n+1} k(k+1)...(k+a)$, thus showing that $\displaystyle P(n)\implies P(n+1)$.

Finally, you'll need to prove that $\displaystyle P(1)$ is true for any $\displaystyle a$.

I hope I've given you enough to go on. Let me know if you need more help.

• Dec 10th 2008, 07:43 AM
james_bond
Suppose $\displaystyle \sum_{k=1}^n\prod_{i=0}^a(k+i)=\frac 1{a+2}\prod_{j=0}^{a+1}(n+j)$. So we need to show that $\displaystyle \sum_{k=1}^{n+1}\prod_{i=0}^a(k+i)=\frac 1{a+2}\prod_{j=0}^{a+1}(n+1+j)$.
$\displaystyle \sum_{k=1}^{n+1}\prod_{i=0}^a(k+i)=\sum_{k=1}^n\pr od_{i=0}^a(k+i)+\prod_{i=0}^a(n+1+i)=\frac 1{a+2}\prod_{j=0}^{a+1}(n+j)+\prod_{i=0}^a(n+1+i)$ by the assumption. So this should be equal to $\displaystyle \frac 1{a+2}\prod_{j=0}^{a+1}(n+1+j)$: $\displaystyle \frac 1{a+2}\prod_{j=0}^{a+1}(n+j)+\prod_{i=0}^a(n+1+i)= \frac 1{a+2}\prod_{j=0}^{a+1}(n+1+j)\leftrightarrow$ $\displaystyle \frac 1{a+2}\prod_{j=0}^{a+1}(n+j)=\frac 1{a+2}\prod_{j=0}^{a+1}(n+1+j)-\prod_{i=0}^a(n+1+i)=$$\displaystyle \left[\prod_{i=0}^a\left(n+1+i\right)\right]\cdot\left(\frac 1{a+2}\cdot \left(n+1+(a+1)\right)-1\right)\leftrightarrow$$\displaystyle \prod_{j=0}^{a+1}(n+j)=\left[\prod_{i=0}^a\left(n+1+i\right)\right]\cdot n$$\displaystyle \leftrightarrow n\cdot (n+1)\cdot\ldots\cdot (n+a+1)=\left[(n+1)\cdot (n+2)\cdot\ldots\cdot (n+a+1)\right]\cdot n$ QED
• Dec 10th 2008, 07:51 AM
mitch_nufc
lol
DR Duncans class by any chance? ;)
• Dec 11th 2008, 01:19 AM
poppy12345
yea
• Dec 11th 2008, 06:19 AM
mitch_nufc
are you still stuck on that or anything? i handed in today, pretty confident everythings right :)
• Dec 11th 2008, 07:17 AM
poppy12345
well i think ive managed but going tomorro. never very confident but neva mind!
• Dec 11th 2008, 07:43 AM
mitch_nufc
im always happy to help if ya stuck... just shout, whats ur name?