I want to prove that for all positive integers  $n$, $2^1+2^2+2^3+...+2^n=2^{n+1}-2$.  By mathematical induction:  1) it holds for $n=1$, since $2^1=2^2-2=4-2=2$  2) if $2+2^2+2^3+...+2^n=2^{n+1}-2$, then prove that  $2+2^2+2^3+...+2^n+2^{n+1}=2^{n+2}-2$ holds.  I have no idea how to proceed with step 2), could you give me a hint?
68440
$\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$.  I don't understand induction so I could use some help.
1119
Prove that  $ n &lt; 2^{n}  $ for all natural numbers $n$.  I tried this with induction: Inequality clearly holds when $n=1$. Supposing that when $n=k$, $k&lt;2^{k}$. Considering $k+1 &lt;2^{k}+1$, but where do I go from here?  Any other methods maybe?
76288
Problem:Let $k$ be an odd positive integer. Prove that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$.  My Attempt: Proof (By Induction on $k$): Let $P(k)$ be the proposition that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$ when $k$ is odd. Then $P(1)$ and $P(3)$ are trivially true. So for $k\geq 5$, we assume that $P(k)$ holds. We would like to show that $P(k+2)$ also holds. In order to do that consider the following sums  $$1^{2}(1^k+2^k+3^k+...+n^k)=1^{k+2}+2^k+3^k+...+n^k$$ $$2^{2}(1^k+2^k+3^k+...+n^k)=2^2*1^k+2^{k+2}+2^2*3^k+...+2^2*n^k$$ $$..$$ $$n^2(1^k+2^k+3^k+...+n^k)=n^2*1^k+n^2*2^k+n^2*3^k+...+n^{k+2}$$ Note that $$1^2(1^k+2^k+3^k+...+n^k)+2^2(1^k+2^k+3^k+...+n^k)+...+n^2(1^k+2^k+3^k+...+n^k)\equiv 0\pmod {\frac{n(n+1)}{2}}$$  Therefore, if we denote $\sum_{i=1}^{n}i^2=s$, then    $(t)(1^k+2^k+3^k+...+n^k)-t+\sum_{i=1}^{n}i^{k+2}\equiv 0\pmod {\frac{n(n+1)}{2}}$ which implies that $P(k+2)$ holds. Hence by PMI we are done.  Now I am a bit hesitant in convincing myself whether this proof is correct or not. This is because I have never seen induction performed in this manner. Any reasons as to why this argument falls would be much appreciated.
99210
Prove that for all  $n \in \mathbb{N}$: $$2^{n-1}(a^n + b^n) \ge (a + b)^n$$ I used induction (for $k = 1,2,...n-1$), and ended up with the following equation:  $$(a + b)(a + b)^{n-1} \le (a + b)(a^{n-1} + b^{n-1})2^{n-2}$$  Now, I have a feeling I'm on the right track, but I'm not totally sure. Could someone give me a pointer one where I should go from here? Any help would be greatly appreciated. Thanks!
60296
I am a CS undergrad and I'm studying for the finals in college and I saw this question in an exercise list:     Prove, using mathematical induction, that $2^n &gt; n^2$ for all integer n greater than $4$   So I started:  Base case: $n = 5$ (the problem states "$n$ greater than $4$", so let's pick the first integer that matches)  $2^5 &gt; 5^2 \implies 32 &gt; 25$ - ok!  Now, Inductive Step:  $2^{n+1} &gt; (n+1)^2$  now expanding  $2 * 2^n &gt; n^2 + 2n + 1$  Well, I can't go on, I don't know how to finish this proof. Could anyone help me with this one?  Also, I know that the statement (inductive hypothesis) is true. Simply, I'll have a number to an exponent $n$ twice, next to $n$ squared and $2n$ (which could be seen as quadratic and linear functions) which "grows" much lower than the exponential one. It could be easily "proved by example" with any $n$ greater than $4$.  I want to know how to prove it algebraically , so my professor does not freak out.  thanks in advance.
92798
So the statement is:  Prove: $$F^2_{n+1} - F^2_{n-1} = F_{2n}$$  How could this be proven with induction?  What about without induction?  For induction I got here: (already tested $n=1$, and assumed $n=k$ held true)  $$F^2_{k+2} - F^2_{k} = F_{2k + 2}$$ $$(F_{k+1} + F_{k})^2 - (F_{k-1} + F_{k-2})^2 = F_{2k+1} + F_{2k}$$ Then you get some cancelation based off the $n=k$ case $$2F_{k+1}F_k + F_k^2 - 2F_{k-1}F_{k-2} - F_{k-2}^2 = F_{2k+1}$$  This is where I am stuck for the induction proof.  I have no idea where to begin with the non-induction proof.
56468
Firstly, this is a homework problem so please do not just give an answer away. Hints and suggestions are really all I'm looking for.  I must prove the following using mathematical induction:     For all $n\in\mathbb{Z^+}$, $1+2+2^2+2^3+\cdots+2^n=2^{n+1}-1$.   This is what I have in my proof so far:     Proof: Let $p\left(n\right)$ be $\sum_{j=0}^n 2^j=1+2+2^2+\cdots+2^n=2^{n+1}-1$. Then $P\left(0\right)$ is    \begin{align} \sum\limits_{j=0}^0 2^j=1=2^1-1.\tag{1} \end{align} Hence    $P\left(0\right)$ is true. Next, for some $k\in\mathbb{Z^+}$, assume    $P\left(k\right)$ is true. Then \begin{align}  \sum\limits_{j=0}^{k+1}2^j&amp;=\left(\sum\limits_{j=0}^k  2^j\right)+2^{k+1}\tag{2}\\ &amp;=2^{k+1}-1+2^{k+1}\tag{3} \\ &amp;=2\cdot 2^{k+1}-1\tag{4}\\ &amp;=2^{k+2}-1\tag{5}\\ &amp;=2^{\left(k+1\right)+1}-1.\tag{6} \end{align}   Therefore, $P\left(n\right)$ holds for all $n$.$\;\;\;\;\blacksquare$   Is everything right? My professor went over the methodology in class quite fast (and I had a bit too much coffee that night) and I want to make sure I have it down for tomorrow night's exam.
47177
There are two ways to try to prove this. One is in the title, the other is its de Morgan counterpart: $n \nmid 2^{2^{2^n+1}+1}+1 \implies n \nmid 2^{2^n+1}+1$. Disproving it requires only one example of course.  Tried using $\gcd(2^a+1, 2^b+1) = 2^{\gcd(a, b)}+1$ (where $a$ and $b$ are odd positive integers), stuck on both ends. I figured out that if $n$ divides $2^n+1$ then n divides both $2^{2^n+1}+1$ and $2^{2^{2^n+1}+1}+1$ but this implication doesn't work backwards (e.g. $n=57$).  Would appreciate some help.  EDIT1 Eric's pointer wasn't enough for me. Trying to bump by editing instead of reposting (sorry, not sure how to).  EDIT2 This is not much but might save some time for someone. Using user101140's notation and the $a^n+b^n$ identity  $f(n) = 2^n+1 = 3 \sum\limits_{k=0}^{n-1} (-2)^k$  $f(f(n)) = 3 \sum\limits_{k=0}^{2^n} (-2)^k$  $f(f(f(n))) = 3 \sum\limits_{k=0}^{2^{2^n+1}} (-2)^k$  Also, $n \mid f(n) \implies n \mid f(f(n))$ is due to $n \mid f(n) \implies f(n) \mid f(f(n))$ so the proof might be something along the lines of $n \mid f(f(n)) \implies f(f(n)) \mid f(f(f(n)))$. (Please don't bash me if that's stupid.)
76244
Let $S(n)$ be the proposition "$2^n &gt; n^2$"  Basis step: $S(5)$ is true, since $2^5 = 32$, $ 32 &gt; 25 = 5^ 2$  Inductive step:  Induction hypothesis:   Assume $S(K)$ is true, $2^K &gt; K^2$.  Then  $2^{K+1} = 2.2^K &gt; K^2 + K^2$   I don't know how to proceed after this. How to complete this proof?
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..
58071
So I'm trying to use mathematical induction to show that for all integers $n \ge 1$ ,  $$ 8|(3^{2n} - 1)$$  (is divisible by 8)  I have my base case: [P(1)],  $3^2 - 1 = 9 - 1 = 8$, since $8|8$, the base case proves true  Assume [P(k)], $ 8 | (3^{2k} - 1)$.  I know that I need to show [P(k+1)], $ 8| (3^{2(k+1)}-1) $, but I'm not sure how to prove this. I've only been using induction for summation, so how could I prove divisibility?
25257
I have this summation and I was attempting to prove it by induction however I have gotten stuck and not sure how to carry on further, if anyone could help point me in the right way that would be much appreciated! $$\sum_{k=0}^{N-1} 2^k = 2^N-1$$  So first I have the base case: $n=2$:  $$\sum_{k=0}^{1} 2^k = 3, \iff 2^2-1=3$$  Then I assumed true for $n=r$ so: $$\sum_{k=0}^{r-1} 2^k = 2^r-1$$  Then I considered $n=r+1$ so I want to show: $$\sum_{k=0}^{r} 2^k = 2^{r+1}-1$$  $$\sum_{k=0}^{r} 2^k = \sum_{k=0}^{r-1} 2^k + (r+1)^\mathrm{th}\text{ term}$$ $$\sum_{k=0}^{r} 2^k = 2^r -1+ (2^{r+1}-1)$$  But now I'm not sure how to go further or whether I got the "$(r+1)^{th}$" term correct or if I can even do this? If anyone can help me complete it and give me tips on induction as I always fail on the inductive step!
49946
How do I prove the following statement by induction?  $$n^2 \lt 2^n$$  $P(n)$ is the statement $n^2 \lt 2^n$  Claim: For all $n \gt k$, where $k$ is any integer, $P(n)$  (since $k$ is any integer, I assume I have to prove this for positive and negative integers)  So let base case be $P(1)$, and I have to prove $P(n)$ for $n \ge 1$ and $n \lt 1$  $P(1)$ is $1^2 \lt 2^1$ which is clearly true.  Induction hypothesis: $k^2 \lt 2^k$  Inductive step $(k+1)^2 \lt 2^{(k+1)}$  $(k+1)^2 = k^2 + 2k + 1$  $k^2 + 2k + 1 \lt 2^k + 2k + 1$ by inductive hypothesis  Not sure how to proceed. Is my previous intuition that I have to prove this for $n \ge 1$ and $n \lt 1$ correct?
37253
Describe all positive integers,n such that $3^{n+1}$divides $2^{3^n}+1$. I am little confused about what the question asks-if it asks me to find all such positive integers, or if it asks me to prove that for every positive integer n,$3^{n+1}$ divides $2^{3^n}+1$. Kindly clarify this doubt and if it's the former part, please verify my solution-n=1.
122259
As title says :     Prove using mathematical induction that $n &lt; 3^n$ for all positive integers $n$.   I came till here  $(k+1)&lt;3^k + 1$  From here I don't have any idea how to show $(k+1)&lt;3^{(k+1)}$ . Please help.
67186
I have to do proof of $(a+b)^n$ and $(a+b)^{n+1}$ with mathematical induction.  I finished the first one $(a+b)^n = a^n + na^{n-1}b+\dots+b^n$.  I however have trouble with the second one, I don't know what to start exactly. Any help/hints?
85986
I am confused as to how to solve this question.  For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds  My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a positive integer  So, $2^{2k} -1 = 3m$   $2^{2k} = 3m+1$  after this, I'm not quite sure where to go.  Can anyone provide any hints?