1
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Hi! Please check out math.meta.stackexchange.com/questions/5020/… to properly format your posts $\endgroup$
    – user418131
    Sep 20, 2018 at 7:09
  • $\begingroup$ Welcome to MSE, can you show the question more easily in your post, and show us what working you have done so far? $\endgroup$
    – MRobinson
    Sep 20, 2018 at 7:09
  • $\begingroup$ Sorry i posted to early i'm updating the post my bad... I really appreciate the help :D 2 sec $\endgroup$
    – Ulrik. S
    Sep 20, 2018 at 7:09
  • $\begingroup$ So apparently you at least tried the inductive step. Can you write what you came up with? $\endgroup$
    – Matti P.
    Sep 20, 2018 at 7:10
  • $\begingroup$ 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 $\endgroup$ Sep 20, 2018 at 7:10

1 Answer 1

1
$\begingroup$
  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).$$

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Ulrik. S
    Sep 20, 2018 at 7:34
  • $\begingroup$ $1 + 2 + ... + k = \sum\limits_{i=0}^k 3^i$ is false, very strange !! $\endgroup$
    – Fred
    Sep 20, 2018 at 7:37
  • $\begingroup$ Arhh i think, that i get your mindset here. It seems that i have over complicated my proof, havn't i? $\endgroup$
    – Ulrik. S
    Sep 20, 2018 at 7:40
  • $\begingroup$ 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)$$? $\endgroup$
    – Ulrik. S
    Sep 20, 2018 at 7:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .