1. ## 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

2. 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
$\displaystyle P_k = \sum_{i=0}^{k} x^i = \frac{(1-x^{k+1})}{1-x}$

test $\displaystyle P_1$

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

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

$\displaystyle P_1$ is true

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

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

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

so

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

$\displaystyle \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}$

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

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

3. 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

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

$\displaystyle \frac{1-x^{\{1+1\}}}{1-x}=\frac{1-x^{2}}{1-x}=\frac{(1-x)(1+x)}{1-x}=1+x$

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

test $\displaystyle P_1$

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

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

$\displaystyle P_1$ is true

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

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

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

so

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

$\displaystyle \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}$

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

so $\displaystyle 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

5. 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)

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

P(k+1)

$\displaystyle \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

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

If P(k) is true, this will be $\displaystyle \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}$

$\displaystyle =\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

$\displaystyle x^0=1$

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

Hence the hypothesis is valid for x not equal to 1

6. 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.