# Simple induction proof, debugging...

I'm getting the hang of induction proofs but just can't seem to complete the inductive step. Meanwhile i beleive what i have made so far is correct.

I have a quantity : $n∈N$

And a statement:$$\sum\limits_{i=0}^n 3^i = \frac{1}{2}(3^{n + 1} - 1)$$

I perform the basis step by assuming that $P(0)$ which gives the following:

$$\sum\limits_{i=0}^0 3^i = \frac{1}{2}(3^{0 + 1} - 1)$$ This proves to be true. So assuming that this is true i can make the assumption of induction since it should be true for all arbitrary numbers, the assumption is as follows:

$$1 + 2 + ... + k = \sum\limits_{i=0}^k 3^i = \frac{1}{2}(3^{k + 1} - 1)$$

In the induction step we prove that if P(k) is true then $P(k) \xrightarrow{} P(k + 1)$

With this assumption we would like to show that:

$$1 + 2 + ... + k + (k + 1) = \sum\limits_{i=0}^{k + 1} 3^i = \frac{1}{2}(3^{(k + 1) + 1} - 1)$$

We use the assumption of induction to create a statement which we would like to prove this is as follows:

$$\sum\limits_{i=0}^{k + 1} 3^i = \bigg ( \sum\limits_{i=0}^{k} 3^i\bigg) + 3^{i + 1} = \frac{1}{2}(3^{(k + 1)+1} - 1)$$

I start solving: $$1 + 2 + ... + k + (k + 1) = (1 + 2 + ... + k) + (k + 1)\\ = \frac{1}{2}(3^{k + 1} - 1) + (k + 1)\\ = \frac{3^{k + 1}-1}{2} +(k + 1)\\ = \frac{3^{k + 1} - 1 + 2(k + 1)}{2}\\ = \text{Result:} = \frac{1}{2}(3^{(k + 1) + 1} - 1)$$

I just can't get to the result which shows that my inductive assumption is true, and can't seem to figure out if i did something wrong or, just can't see forest from trees... Thanks for all the help. It has be solved by induction.

– user418131
Sep 20, 2018 at 7:09
• Welcome to MSE, can you show the question more easily in your post, and show us what working you have done so far? Sep 20, 2018 at 7:09
• Sorry i posted to early i'm updating the post my bad... I really appreciate the help :D 2 sec Sep 20, 2018 at 7:09
• So apparently you at least tried the inductive step. Can you write what you came up with? Sep 20, 2018 at 7:10
• Im not sure if this question has been given specifically to do with induction, but you don’t need it to prove the identity given Sep 20, 2018 at 7:10

1. the formula is true for $n=0$.

2. Now suppose that $P(n)=\frac{1}{2}(3^{n+1}-1)$ for some $n \in \mathbb N \cup \{0\}$.

3. With the aid of 2. you have to show that $P(n+1)=\frac{1}{2}(3^{n+2}-1)$:

Since $P(n+1)=P(n)+3^{n+1}$, we get by 2. :

$P(n+1)=\frac{1}{2}(3^{n+1}-1)+3^{n+1}$.

It is your turn to show that

$$\frac{1}{2}(3^{n+1}-1)+3^{n+1}=\frac{1}{2}(3^{n+2}-1).$$

• Hello, looks very nice, would you have time to look at my re-updated post. And give me some thoughts of what i did wrong? Sep 20, 2018 at 7:34
• $1 + 2 + ... + k = \sum\limits_{i=0}^k 3^i$ is false, very strange !!
– Fred
Sep 20, 2018 at 7:37
• Arhh i think, that i get your mindset here. It seems that i have over complicated my proof, havn't i? Sep 20, 2018 at 7:40
• Since i have to prove that it is true for n + 1 why isn't it $$\frac{1}{2}(3^{n+1} - 1) + \frac{1}{2}(3^{n+1} - 1)$$? Sep 20, 2018 at 7:49