10
$\begingroup$

For example if I want to prove that $2^n - 1 = 1 + 2 + 4 + 8 +...+ 2^{n-1}$ I can obviously use induction and that is accepted. But I can also collapse it like:

To Prove $2^n = S(n)$:

  1. $S(n) = (1 + 1) + 2 +...+ 2^{n-1}$
  2. $S(n) = (2 + 2) + 4 + 8 +...+2^{n-1}$
  3. $S(n) = (4 + 4) + 8 +...+2^{n-1}$

and so on until $S(n) = 2^{n-1} + 2^{n-1} = 2^n$

Is this method of collapsing considered a legitimate and presentable proof?

| cite | improve this question | |
$\endgroup$
  • 22
    $\begingroup$ Actually the phrase "so on until" is a code for "induction". But yes, once you know induction, you can wrote "so on until" in place of your "induction" proof. $\endgroup$ – GEdgar Jan 3 '16 at 13:30
  • 1
    $\begingroup$ Oh ok. I've self learned induction but I haven't really "studied" it as such. $\endgroup$ – Airdish Jan 3 '16 at 13:32
  • 3
    $\begingroup$ Also in1. ,2. ,3. ,etc do not write $2^n$ on the LHS to start.That is what you are trying to prove. Call it S(n). Eventually reaching$ S(n)=2^{n-1}+2^{n-1}=2^n$. As GEdgar points out, "eventually " or "so on until" means "by induction." $\endgroup$ – DanielWainfleet Jan 3 '16 at 14:03
  • 3
    $\begingroup$ Using the idea of collapsing or anything like that should be fine (at least outside the setting of a class where they want to emphasize rigor). It's intuitive and it's obvious that the procedure works and can be continued to its end. You'd definitely find things like this in mathematical writing, since it can serve to illuminate the meaning behind proofs beyond what utterly rigorous proofs can do. $\endgroup$ – Milo Brandt Jan 3 '16 at 16:53
  • $\begingroup$ @user254665 I fixed the LHS problem $\endgroup$ – Airdish Jan 4 '16 at 3:50
23
$\begingroup$

Well, sort of, but in fact, writing proofs like the one you want to write is why induction exists. Whenever people say something like "and so on until", they're expressing your intuition that it's possible to continue the argument by induction. The whole point of the method of induction is to make intuitions like this one precise.

Let $S(k)=2^k + 2^k + 2^{k+1} + 2^{k+2} + ... + 2^{n-1}$. Then what we want to show is that $S(0) = 2^n$. Your proof basically amounts to saying $S(0) = S(1) = S(2) = ...$ "and so on", until we get $S(0) = S(n-1)$. Notice that $S(n-1) = 2^{n-1} + 2^{n-1}$, which obviously equals $2^n$. So we get $S(0) = 2^n$. To phrase this as a proof by induction, we're going to prove by induction that $S(0) = S(k)$ for all $k<n$, thus we'll obtain $S(0)=S(n-1)$ at the end.

Obviously, $S(0) = S(0)$. Now suppose $S(0) = S(k)$. Then:

$$\begin{align}S(0) &= S(k) \\&= 2^k + 2^k + 2^{k+1} + 2^{k+2} + ... + 2^{n-1} \\&= 2\cdot2^k + 2^{k+1} + 2^{k+2} + ... + 2^{n-1} \\&= 2^{k+1} + 2^{k+1} + 2^{k+2} + ... + 2^{n-1}\\&=S(k+1)\end{align}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I thought that induction worked on the premise that for S(n), you first take some value k, input it: S(k) and consider it to be true. Then you take S(k+1) and show that it resembles S(k)? $\endgroup$ – Airdish Jan 3 '16 at 13:31
  • 3
    $\begingroup$ @S.Mo In induction we have a predicate $P(n)$, that is, a true-false statement into which we can plug $n$ like a variable, for example, an equation involving $n$. We then show that if $P(n)$ is true for any $n$, then $P(n+1)$ is true. Using phrasing like "show that it resembles" makes it seem like induction is just a method of shuffling symbols around. $\endgroup$ – Jack M Jan 3 '16 at 14:10
  • $\begingroup$ I'd have thought that an induction proof for this would look more like this: $\endgroup$ – Airdish Jan 3 '16 at 17:05
  • $\begingroup$ $S(n) = 1 + 1 + 2 + 4 +...2^{n-1}$ Assuming that $2^{k} = S(k) = 1 + 1 + 2 + 4 + 8 +...2^{k-1} $ $S(k+1) = (1 + 1 + 2 + 4 + 8 + ... + 2^{k-1}) + 2^k$ It follows that $ S(k+1) = S(k) + 2^k$ $S(k) + 2^k = 2^k + 2^k = 2^ {k+1}$ Therefore $S(k+1) = 2^{k+1}$ Hence proved that $S(n) = 2^n$ $\endgroup$ – Airdish Jan 3 '16 at 17:05
  • $\begingroup$ Please correct me if I'm wrong. $\endgroup$ – Airdish Jan 3 '16 at 17:05
7
$\begingroup$

This depends very much on the degree of rigour you want.

If you want to be really rigorous, or need to, then you would need to formalize “so on” by showing by induction that $$ 1 + \sum_{i=0}^{n-1} 2^i = 2^k + \sum_{i=k}^{n-1} 2^i \quad \text{for all $k = 0, \dotsc, n$}, $$ which shows the statement for $k = n$.

If you are satisfied with less rigour, and I think most (read: nearly all) mathematicians will be in a case like this, then “so on” is good enough, as the idea behind your proof is pretty clear. It is, however, important that you are able to give a formal proof.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Of course: for every finite $n$ you have absolutely convergent series which allows you to manipulate it's memebers in a way you are doing it. Although it seems if you want to present you proof in a most formal way, induction will take up less space.

| cite | improve this answer | |
$\endgroup$
-4
$\begingroup$

the consensus here seems to be "yeah, the proof is ok but rather informal since it invokes induction 'coded' in the 'and-so-on' statement". I don't agree. Imho this is no proof at all and there is no induction argument given.

  1. The Argument starts with the claim (short of subtracting one from both sides of the equation). Why bother and continue?
  2. The modifications made in order to get to the next line are completely unclear to me. Are all the elements in the series doubled? Then the result (left side) should be doubled as well but it isn't?
| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ It's true that the author shouldn't be writing $2^n=\ldots$ until the last line - however, this is not a structural error in their proof, as they do not use the assumption. It's merely a stylistic problem. The manipulation from one line to the next is that they combine the terms $1+1$ into $2$, then $2+2$ into $4$, then $4+4$ into $8$ and so on. $\endgroup$ – Milo Brandt Jan 4 '16 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.