# Proof by contradiction and mathematical induction

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

• I would only know by induction and using the fact it is a geometric series..so I am interested in proof by contradiction. +1 – Chinny84 Jun 15 '15 at 9:34
• @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. – Adayah Jun 15 '15 at 9:49
• 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? – Minjae Jun 15 '15 at 10:30

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}$.

• What do you mean by 'Then evidently k>1.'? – Minjae Jun 15 '15 at 10:33
• I mean, isn't it too early to show that k can't be smaller than 1? What's the point for that? – Minjae Jun 15 '15 at 10:35
• 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). – drhab Jun 15 '15 at 10:42
• 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. – drhab Jun 15 '15 at 10:58
• Got it. So, that's the whole point of proof by contradiction, right? – Minjae Jun 15 '15 at 11:21