I'm trying to prove that for all positive integers $a$, that $2^a = 2$. Obviously, I know this is false, but I was given an induction proof and I need to find the error. The base case is that for $a = 1$, it's true that $2^1 = 2$. For the induction step, we let $x$ be an arbitrary positive integer. The induction hypothesis is that $2^y = 2$ for all integers $y$ such that $1 \leq y \leq x$, with the same restriction on $x$ as mentioned. We need to prove that $2^{x + 1} = 2$. $2^{x+1} = \frac{2^x \cdot 2^x}{2^{x - 1}}$ $= \frac{2 \cdot 2}{2}$ by the induction hypothesis $= 2$ This completes strong induction, so $2^a = 2$ for all positive integers $a$.
122397
Donald Knuth &quot;The Art of Computer Programming&quot; Section 1.2.1 has an exercise No.2, the solution to which I don't understand. Exercise:  There must be something wrong with this proof. What is it? Theorem. Let $a$ be any positive number. For all positive integers $n$ we have $a^{n-1}=1$. Proof. If  $n = 1, a^{n-1}=a^{1-1}=a^0=1$. And by induction, assuming that the theorem is true for $1, 2, ..., n$, we have $a^{(n+1)-1}=a^n=\frac{a^{n-1}\times a^{n-1}}{a^{(n-1)-1}}=\frac{1\times1}{1}=1$; so the theorem is true for $n+1$ as well.  As far as I understand the proof by induction, the solution should be approximately following:$a^{1-1}=1$Assume that $a^{n-1}=1$;Therefore $a^{(n+1)-1}=1\times a$;So $a^{(n+1)-1}$ does not equal $a^{n-1}$ and does not equal $1$, unless $a=1$ The solution to exercise reads:  The theorem has not been proved for $n=2$; in the second part of the proof, take $n=1$; we assume there that $a^{-1}=1$. If this condition is true (so that $a=1$), the theorem is indeed valid.  I want to compare it to another, correct, proof by induction in the example from :  Adding up Odd Numbers $1+3+5+...+(2n−1)=n^2$  Show it is true for $n=1$ $1=1^2$ is True Assume it is true for $n=k$ $1+3+5+...+(2k−1) = k^2$ is True (An assumption!) Now, prove it is true for $(k+1)$ $1 + 3 + 5 + ... + (2k−1) + (2(k+1)−1) = (k+1)^2$We know that $1 + 3 + 5 + ... + (2k−1) = k^2$ (the assumption above),so we can do a replacement for all but the last term:$k^2 + (2(k+1)−1) = (k+1)^2$Now expand all terms:$k^2 + 2k + 2 − 1 = k^2 + 2k+1$And simplify:$k^2 + 2k + 1 = k^2 + 2k + 1$They are the same! So it is true.So: $1 + 3 + 5 + ... + (2(k+1)−1) = (k+1)^2$ is True   Returning to the first example, I didn't quite understand the meaning of the phrase  The theorem has not been proved for $n=2$;  In the second (correct) proof there is no proving that it holds for $n=2$, despite covering the same topic. And Knuth himself has the proof of the theorem $1+3+5+...+(2k−1) = k^2$ similar to the one above, where he too doesn't prove it for $k=2$. So what did he mean by this phrase? Does he mean that there already is an exception in the rule stated when we take arbitrary $n$, for example $n=2$, so therefore it wouldn't hold for all examples anyway? But taking arbitrary numbers and putting it into equation instead of $n$ doesn't seems to be an effective and systematic way to debunk such proofs. How would you explain what is wrong with the exercise?
8096
I am trying to prove that $n^2 \leq 2^n$ for all natural $n$ with $n \ne 3$. My steps are:    induction base case: $n=0:$ $0² \leq 2⁰$ which is okay.    inductive step: $n \rightarrow n+1:$ $(n+1)²\leq2^{n+1}$ $$(n+1)^2 = n^2 + 2n + 1 = ...help...\leq 2^{n+1}$$   I know the bernoulli inequality but don't know where to use it, if I even need to. I have problems when it comes to proving things which are based on orders..
19168
Let $a$ be a nonzero number and $m$ and $n$ be integers. Prove the following equality: $a^{m+n}=a^{m}a^{n}$  I'm not really sure what direction to go in. I'm not sure if I need to show for $n$ positive and negative separately or is there an easier way. Can you use induction on integers?  My attempt: 1) Base case $m=0$. Prove that $a^{m+n}=a^m a^n$. Is true.  2) Assume the result holds for $m$.  So I want to prove it holds for $m+1$.  So I know that $a^{m+n}=a^ma^n$. So does this imply that: $a^{m+n+1}= a^{m+1+n}= a^{m+1}a^n$? Am I going in the right direction? I'm not sure what to do next...
55620
So I need to prove the inequality :  $$n &lt; 2^n$$  by Induction.  What I have done so far is :     Step $1$: Prove that the statement is true for $n=1$   $$1&lt;2^1$$ (true)      Step $2$:    Prove that, if $p(n)$ is true, then $p(n+1)$ is also true.      Assume that $p(n): n &lt; 2^n$ is true. then :      (Add $1$ on both side to get $n+1$) : $$n+1 &lt; 2^n +1$$      (Multiply the original inequality by $2$ to get $2^{n+1}$ ) :   $$2^{n+1} &lt; 2^n . 2$$   I don't know where to go from here. In fact, I am not sure whether what I did is true or not. I appreciate any insight and help.
115268
Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.   Today I wrote calculus exam, I had this problem given.  I have the feeling that I will get $0$ points for my solution, because I did this:   Base Case: $n=1$ $$\sum_{k=1}^{1} \binom 1 1 = 1 =  2^1 -1 .$$  Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$  Induction Step: $n \rightarrow n+1$ $$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$  Please show me my mistake because next time is my last chance in this class.
13650
I don't know how to explain or how to prove the following statement  If $n=ab$ and $a,b \in \mathbb{N}$ then $2^a-1 \mid 2^n-1$.  Any ideas? Perhaps an induction?  Thanks in advance.
82812
Prove that $$3^n &gt; n^2$$  I am using induction and I understand that when $n=1$ it is true. The induction hypothesis is when $n=k$ so $3^k&gt;k^2$. So for the induction step we have $n=k+1$ so  $3^{k+1} &gt; (k+1)^2$ which is equal to $3\cdot3^k &gt; k^2+2k+1$. I know you multiple both sides of the induction hypothesis by $3$ but I'm not sure what to do next.
112406
Show that every positive integer is a sum of one or more numbers of the form $2^r3^s,$ where $r$ and $s$ are nonnegative integers and no summand divides another.   From:   I see they mean that:  $$n-1 = \sum_{k=1}^{x} 2^{r_k} 3^{s_k}$$  By induction hypothesis. Then:  $$n = \sum_{k=1}^{x} 2^{r_k} 3^{s_k} + 1$$  Then how to proceed by $n/2$? How can you say that:  $$\frac{n}{2} = \sum_{k=1}^{x} 2^{r_k} 3^{s_k} $$  Where did the $1$ go? And how can you assume it works for $\frac{n}{2}$ (the hypothesis)?
76578
I'm trying to prove $2^b-1$ does not divide $2^a + 1$ for $a,b&gt;2$. Can someone give a hint in the right direction for this?
23149
For any natural number $n\ge 1$, given pairs $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ of integer numbers, there exist integer number $c$ and $d$ such that  $$\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$$    My initial approach is  Base Case: $(a_1^2+b_1^2) = a_1^2+b_1^2$ which is true. (Although it is trivial)  Prove the statement is true when $n=2$: We have $$(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$$ (Thanks André Nicolas for pointing it out)   So if $a,b,c,d$ are integers, $ac,bd,ad,bc$ are all integers and integers are closed under addition and subtraction. Hence $(ac-bd),(ad+bc)$ are integers.   Inductive Hypothesis: $\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$ is true  Inductive Step: $$\prod_{i=1}^{n+1}(a_i^2+b_i^2) = \prod_{i=1}^{n}(a_i^2+b_i^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2)$$  Where $c$ and $d$ are integers.   But when we apply $n=2$, we have  $(c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (e^2 + f^2)$ where $e$ and $f$ are integers.  Hence, by the principle of induction, the statement we needed to prove is true.
517
Let $a,b&gt;2$ be positive integers. We need to show that $2^a +1$ is not divisible by $2^b-1$.  Could any one give me hint?
41594
I want to prove $gcd(a, a+2)$ = 1 or 2 for every integer $a$.   I know that (a, a+2) is equal to the least positive value of $ax + (a+2)y$, where $x, y \in \mathbb{Z}$. However, I'm a little stuck at this point. I'm thinking I should split apart the problem into two cases, one where $a$ is odd and one where $a$ is even? Any suggestions? Thanks.
22704
Prove that $\gcd(2^{2^m}+1,2^{2^n}+1)=1$ if $m,n$ are positive integers.  Let $d=\gcd(2^{2^m}+1,2^{2^n}+1)$, then $d\mid 2^{2^m}+1$ and $d\mid2^{2^n}+1$ and then $d\mid2^{2^m}+1-2^{2^n}-1$, i.e. $d\mid2^{2^m}-2^{2^n}$ where we have taken $m&gt;n$. Thus $d\mid2^{2^n}(2^{2^{m-n}}-1)$, but $d \nmid 2^{2^n}$ thus $d\mid2^{2^{m-n}}-1$.  Then how will I proceed??
115524
The problem is following, prove that:  $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$    I've tried solving this problem using mathematical induction, but I don't think that i did it correctly. Here's what i've done  $1.\ b=1\ (Basis)$  $$b!| (a+1)(a+2)...(a+b)$$ $$1 | a+1 \text{, which is true}$$  $2.\ b=k\ (Induction\ Hypothesis)$  $$k! | (a+1)(a+2)...(a+k)\text{, we assume it's true}$$ $$k!*n = (a+1)(a+2)...(a+k)\text{, n is some positive integer}$$  $3.\ b=k+1\ (Inductive\ Step)$  In order to prove I should get:  $$(k+1)!*m = (a+1)(a+2)...(a+k)(a+k+1)\text{, where m is some positive integer}$$ $$(a+1)(a+2)...(a+k)(a+k+1) = k!*n*(a+k+1)$$ $$(a+1)(a+2)...(a+k)(a+k+1) = (k+1)!*n + k!*n*a$$ $$(a+1)(a+2)...(a+k)(a+k+1) - a(a+1)(a+2)...(a+k) = (k+1)!*n$$ $$(a+1)(a+2)...(a+k)(k+1) = (k+1)!*n$$  And as you can see I'm returning at the beginning.  Also I've tried to use the fact that in b consecutive numbers, there must be at least one that divides b, but since i eliminate that number (because I couldn't be sure that the quotient is divisible with (b-1) or (b-2) or ... or 2. And after this i can't continue with (b-1) using this method, because it's not necessary for the other (b-1) to be consecutive.
120645
I tried proving it but I'm quite skeptical about it:  $(\Rightarrow )$ Assume $x&lt;y$. Clearly, the base case for the induction is done. Assume $x^k&lt;y^k$ for some $k\in \mathbb{N}$.  Now, $x^{k+1}=x^k\cdot x&lt;y^k\cdot y=y^{k+1}$.   $(\Leftarrow )$ Assume for contradiction that $x\not&lt; y$. Then $y\le x$. Now, suppose $y\ne x$. Then $y&lt;x$. It follows that $y^n&lt;x^n$ for every $n\in \mathbb{N}$ from $(\Rightarrow )$. This contradicts our hypothesis. Also, if $y\not&lt; x$ then $x=y$. Then $y^n=x^n$ for every $n\in \mathbb{N}$ which also contradicts our hypothesis.  Is this proof correct?
72210
I am trying to prove that $\dfrac{(2n)!}{2^n}$  is integer. So I have tried it by induction, I have took  $n=1$, for which we would have $2/2=1$ is integer. So for $n=k$ it is true, so now comes time to proof it for $k+1$, $(2(n+1))!=(2n+2)!$, which is equal to $$1 \times 2 \times 3 \times \cdots \times (2n) \times (2n+1) \times (2n+2),$$ second term would be $$2^{n+1}=2 \times 2^n$$ Finally if we divide $(1 \times 2 \times 3 \times \cdots \times (2n) \times (2n+1) \times (2n+2)$ by $2^{n+1}=2 \times 2^n$,and consider that,$(2n)!/(2^n)$  is integer, we get $(2n+1) \times (2n+2)/2=(2n+1) \times 2 \times (n+1)/2$, we can cancel out $2$, we get $(2n+1)(n+1)$ which is definitely integer. I am curious this so simple? Does it means that I have proved correctly?
47984
Prove for any $a&gt;1$ there exist a natural number, $N$, such that $a^n&gt;n$ for all $n \ge N$  My attempt:  By definition, for $N$ to be a natural number $1\le N \le ∞$ for any integer $N$.  By induction, the base case $n=1$ is true because $a^1&gt;1$ which is true.  Now assume that $a^k&gt;k$ is true, then it is also true for $n= k+1$.  Hypothesis  $a^{k+1}&gt;k+1$  Now I am not sure if I am on the right track