2
$\begingroup$

$\sum_{i=1}^n {2\over3^i}={2\over3}+{2\over9}+\dots+{2\over3^n}=1-{({1\over3})^n}$

I had this problem in class and we proved using 2 different methods: contradiction and mathematical induction. I thought it was understood, I just got bumped into certain point.

Please point it out which step I'm thinking wrong.

For the contradiction, We assume that there is some integer n for which $i=1$ is false. And we are applying smaller positive integer smaller than 1.

for the smallest n, ${2\over3}+{2\over9}+{\dots}+{1\over3^{n-1}}$ indicates that our assumption $i=1$ is false.

(I don't remember how the calculation was made for this proof by contradiction.)

Therefore, our assumption was true.

For induction,

Try out the base case with applying $i=1$ inductive hypothesis would be ${2\over3}=1-{1\over3}$

What would be the next step?

$\endgroup$
3
  • $\begingroup$ I would only know by induction and using the fact it is a geometric series..so I am interested in proof by contradiction. +1 $\endgroup$
    – Chinny84
    Commented Jun 15, 2015 at 9:34
  • $\begingroup$ @Chinny84: A proof by contradiction = proof by induction + proof of induction itself. I.e. suppose for contradiction there is $n$ for which equality doesn't hold and take smallest such $n$. By induction base proof, $n \neq 1$. So $n = k+1$ for some $k$ and equality holds for $k$ since $k < n$. That contradicts induction step proof. $\endgroup$
    – Adayah
    Commented Jun 15, 2015 at 9:49
  • $\begingroup$ I don't get 'By induction base proof, n≠1. So n=k+1 for some k and equality holds for k since k<n' How come n≠1 leads to n=k+1? $\endgroup$
    – Minjae
    Commented Jun 15, 2015 at 10:30

1 Answer 1

2
$\begingroup$

By contradiction.

Assume that $\sum_{i=1}^{n}\frac{2}{3^{i}}\neq1-\frac{1}{3^{n}}$ for some $n\in\mathbb{N}$ and let $k$ be the smallest positive integer with $\sum_{i=1}^{k}\frac{2}{3^{i}}\neq1-\frac{1}{3^{k}}$.

Then evidently $k>1$.

The minimality of $k$ implies that $\sum_{i=1}^{k-1}\frac{2}{3^{i}}=1-\frac{1}{3^{k-1}}$ so that: $$\sum_{i=1}^{k}\frac{2}{3^{i}}=\sum_{i=1}^{k-1}\frac{2}{3^{i}}+\frac{2}{3^{k}}=1-\frac{1}{3^{k-1}}+\frac{2}{3^{k}}=1-\frac{1}{3^{k}}$$

A contradiction has been found and we conclude that $\sum_{i=1}^{n}\frac{2}{3^{i}}=1-\frac{1}{3^{n}}$ for any $n\in\mathbb{N}$.

$\endgroup$
6
  • $\begingroup$ What do you mean by 'Then evidently k>1.'? $\endgroup$
    – Minjae
    Commented Jun 15, 2015 at 10:33
  • $\begingroup$ I mean, isn't it too early to show that k can't be smaller than 1? What's the point for that? $\endgroup$
    – Minjae
    Commented Jun 15, 2015 at 10:35
  • $\begingroup$ For $k=1$ the statement $\sum_{i=1}^{k}\frac{2}{3^{i}}=1-\frac{1}{3^{k}}$ is evidently a true statement. I suspect you agree with me that $\frac23=1-\frac13$. This justifies the conclusion that $k\neq1$ (it is the smallest positive integer for wich the statement is not true). $\endgroup$
    – drhab
    Commented Jun 15, 2015 at 10:42
  • $\begingroup$ The point of showing that $k>1$ is in fact showing that $k$ has a predecessor - $k-1$ that is - for wich the statement is true. In the proof we make use of this fact. $\endgroup$
    – drhab
    Commented Jun 15, 2015 at 10:58
  • $\begingroup$ Got it. So, that's the whole point of proof by contradiction, right? $\endgroup$
    – Minjae
    Commented Jun 15, 2015 at 11:21

You must log in to answer this question.

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