# proof by induction

• June 2nd 2010, 11:27 AM
alex83
proof by induction
pls i need help to proof the following by induction technique

(summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
where x does not equal to 1
first i substituted the letter i by a
then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

thank you
• June 2nd 2010, 11:42 AM
Amer
Quote:

Originally Posted by alex83
pls i need help to proof the following by induction technique

(summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
where x does not equal to 1
first i substituted the letter i by a
then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

thank you

$P_k = \sum_{i=0}^{k} x^i = \frac{(1-x^{k+1})}{1-x}$

test $P_1$

$\sum_{i=0}^1 x^i = x^0 + x=1+x$

$\frac{1 - x^{1+1}}{1-x} = 1+x$

$P_1$ is true

suppose that $P_k$ is true try $P_{k+1}$ is true

$\sum_{i=0}^{k+1} x^i = x^{k+1}+\sum_{i=0}^{k} x^i$

but $\sum _{i=0}^{k} x^k = \frac{1- x^{k+1}}{1-x}$

so

$\sum_{i=0}^{k+1} x^i = \frac{1- x^{k+1}}{1-x} + x^{k+1}$

$\frac{1- x^{k+1}}{1-x} = \frac{1- x^{k+1} + x^{k+1} - x^{k+2}}{1-x} = \frac{1-x^{k+2}}{1-x}$

$\sum_{i=0}^{k+1} x^i = \frac{1-x^{k+2}}{1-x}$

so $P_{k+1}$ is true the proof end
• June 2nd 2010, 11:44 AM
oldguynewstudent
Quote:

Originally Posted by alex83
pls i need help to proof the following by induction technique

(summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
where x does not equal to 1
first i substituted the letter i by a
then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

thank you

Start this way: Let n=1, then for the LHS

$\sum_{i=0}^{1}x^{i}=x^{0}+x^{1}=1+x$ and for the RHS

$
\frac{1-x^{\{1+1\}}}{1-x}=\frac{1-x^{2}}{1-x}=\frac{(1-x)(1+x)}{1-x}=1+x
$
• June 2nd 2010, 12:03 PM
alex83
Quote:

Originally Posted by Amer
$P_k = \sum_{i=0}^{k} x^i = \frac{(1-x^{k+1})}{1-x}$

test $P_1$

$\sum_{i=0}^1 x^i = x^0 + x=1+x$

$\frac{1 - x^{1+1}}{1-x} = 1+x$

$P_1$ is true

suppose that $P_k$ is true try
$P_{k+1}$ is true

$\sum_{i=0}^{k+1} x^i = x^{k+1}+\sum_{i=0}^{k} x^i$

but $\sum _{i=0}^{k} x^k = \frac{1- x^{k+1}}{1-x}$

so

$\sum_{i=0}^{k+1} x^i = \frac{1- x^{k+1}}{1-x} + x^{k+1}$

$\frac{1- x^{k+1}}{1-x} = \frac{1- x^{k+1} + x^{k+1} - x^{k+2}}{1-x} = \frac{1-x^{k+2}}{1-x}$

$\sum_{i=0}^{k+1} x^i = \frac{1-x^{k+2}}{1-x}$

so $P_{k+1}$ is true the proof end

thank you
but the question has a condition that x does not equals to 1
i thought we are not allowed to use the (1) in our assumption
is this true
thnx again
• June 2nd 2010, 12:14 PM
Quote:

Originally Posted by alex83
pls i need help to proof the following by induction technique

(summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
where x does not equal to 1
first i substituted the letter i by a
then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

thank you

Hi alex83,

P(k)

$\sum_{i=0}^kx^i=\frac{1-x^{k+1}}{1-x}$

P(k+1)

$\sum_{i=0}^{k+1}x^i=\frac{1-x^{k+2}}{1-x}$

Try to prove that P(k) being true causes P(k+1) to be true

Proof

$\sum_{i=0}^{k+1}x^i=\sum_{i=0}^kx^i+x^{k+1}$

If P(k) is true, this will be $\frac{1-x^{k+1}}{1-x}+x^{k+1}=\frac{1-x^{k+1}}{1-x}+\frac{(1-x)x^{k+1}}{1-x}$

$=\frac{1-x^{k+1}+x^{k+1}-x^{k+2}}{1-x}=\frac{1-x^{k+2}}{1-x}$

Hence P(k) true causes P(k+1) to be true

Therefore if the formula is valid for i=0, it's valid for i=1 and therefore for i=2,
for i=3, for i=4, for i=5........ to infinity

To check the validity for i=0

$x^0=1$

$\frac{1-x^{0+1}}{1-x}=\frac{1-x}{1-x}=1$

Hence the hypothesis is valid for x not equal to 1
• June 2nd 2010, 12:59 PM
Quote:

Originally Posted by alex83
thank you
but the question has a condition that x does not equals to 1
i thought we are not allowed to use the (1) in our assumption
is this true
thnx again

Hi alex83,

x cannot be 1 as 1-x in the denominator would be zero,
and we need to avoid having a divide by zero.

Choosing i=1 would be testing the formula for the first 2 terms in the sum,
though you may start at i=0, which strictly speaking is more correct.
If the sum was from i=1 to n, we test the formula for i=1,
but since the sum starts at i=0, then i=0 gives the first term in the sum.