Theorem : For every natural number $p$: $$\sum^p_{i=0} 2^i = 2^{p+1}-1$$ I trieed to demonstrate the theorem using induction  Demonstration :  $1)$ If we have $p=0$ then we get $2^0=2^{0+1}-1$ that is always true. $2)$ Supposing that the first statement is true then we get that $$\sum^{p+1}_{i=0} 2^i = 2^{p+2}-1$$ Now we know that: $$\sum^{p+1}_{i=0} 2^i - \sum^p_{i=0} 2^i = 2^{p+1}$$ and if that is true, must be also true that: $$2^{p+2}-1-(2^{p+1}-1) = 2^{p+1}$$ $$2^{p+2}-1-(2^{p+1}-1)=2^{p+2}-2^{p+1}=2^{p+1}(2^1-2^0)=2^{p+1}$$ QED  Is this a valid demonstration?
37643
$$\sum_{k=0}^nq^k = \frac{1-q^{n+1}}{1-q}$$  I want to prove this by induction. Here's what I have.  $$\frac{1-q^{n+1}}{1-q} + q^{n+1} = \frac{1-q^{n+1}+q^{n+1}(1-q)}{1-q}$$  I wanted to factor a $q^{n+1}$ out of the second expression but that 1- is screwing it up...
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.
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..
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)?
9980
This is my last homework problem and I've been looking at it for a while. I cannot nail down what is wrong with this proof even though its obvious it is wrong based on its conclusion. Here it is:     Find the flaw in the following bogus proof by strong induction that   for all $n \in \Bbb N$, $7n = 0$.      Let $P(n)$ denote the statement that $7n = 0$.      Base case: Show $P(0)$ holds.      Since $7 \cdot 0 = 0$, $P(0)$ holds.      Inductive step: Assume $7·j = 0$ for all natural numbers $j$ where $0 \le j \le k$ (induction hypothesis). Show $P(k + 1)$: $7(k + 1) = 0$.      Write $k + 1 = i + j$, where $i$ and $j$ are natural numbers less than $k + 1$.  Then, using the induction hypothesis, we get $7(k + 1) = 7(i + j) = 7i + 7j = 0 + 0 = 0$. So $P(k + 1)$ holds.      Therefore by strong induction, $P(n)$ holds for all $n \in \Bbb N$.   So the base case is true and I would be surprised if that's where the issue is.  The inductive step is likely where the flaw is. I don't see anything wrong with the strong induction declaration and hypothesis though and the math adds up! I feel like its so obvious that I'm just jumping over it in my head.
71960
This question is from Elementary Number Theory by W. Edwin Clark.      Is $2^n - 1$ always prime, or not? Prove.   Is this a start? $x^n - 1 = ( x - 1)(1 + x + x^2 \cdots x^{n - 1})$. So, $2^n - 1 = \sum \limits _{i = 0}^{n - 1} 2^i.$  Will I reach a solution through the above, or is there any other way?  I know that the property doesn't hold true for $n = 1,4,6$ et al but I want an algebraic proof.
6856
Here is a problem which i have not been able to do for quite sometime.   For $n \geq 2$, show that $n \nmid 2^{n}-1$.   I have thought of proving this in two ways: One by using induction which didn't actually work. Next by Fermat's little theorem we have $2^{p-1} \equiv 1 \ (\text{mod} \ p)$, which actually says that for $p \mid 2^{p}-2$. But i couldn't proceed more than this. Any ideas by which i can actually solve the problem?
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.
47399
I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: $$0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}=n(1+n)2^{n-2} $$
59317
I was asked to show that $\forall n\in \mathbb N$ there exist a $p\in \mathbb N^\ast$ such that $$(1+\sqrt{2})^n = \sqrt{p} + \sqrt{p-1}$$   I used induction but it wasn't fruitful, so I tried to use the binomial expansion of $(1+\sqrt{2})^n$ but it seems I lack some insight to go further.   Any hint is welcomed.
60937
These are just the examples from my textbook, but I don't think it did not explain well.  One of the problem was to prove the inequality   $$n&lt;2^n$$  for all integers $n$.  I understand we assume if $P(n)$ is true, $P(k+1)$ is true.  Thus $k+1&lt; 2^{k+1}$  But in the text book, they added one more line that I don't understand:  $$k+1&lt;2^k+1 \le 2^k+2^k=2\cdot2^k=2^{k+1}$$  I understand  $$k+1&lt;2^{k+1}$$  But how do I know $2^k+1$ is larger than $k+1$, and smaller than $2^{k+1}$?  I have one another example just in case,  proving $2^n&lt;n!$ using induction.  $$2^{k+1}=2\cdot 2^k&lt;2\cdot k!&lt;(k+1)k!=(k+1)!$$  I understand we should start with $2^{k+1}&lt;(k+1)!$, but  Where did $2\cdot k!$ come from? Textbook says it came from inductive hypothesis, but I still don't get it.  Please advise.
78732
Prove by mathematical induction that:  $$\forall n \in \mathbb{N} : \sum_{k=1}^{2n} \frac{(-1)^{k+1}}{k} = \sum_{k=n+1}^{2n} \frac{1}{k} $$  Step 1: Show that the statement is true for $n = 1$:  LHS = $$\frac{(-1)^{1+1}}{1} = 1$$  RHS = $$\frac{1}{1} = 1$$  Step 2: Show that "if true for n = p, then true for n = p + 1":  Starting with the LHS of equality for $n = p + 1$ and try to get to the RHS by using the equality for $n = p$. Simplifying:  $$\sum_{k=1}^{2(p+1)} \frac{(-1)^{k+1}}{k} = \sum_{k=1}^{2p+2} \frac{(-1)^{k+1}}{k}$$  Breaking out the first two term:  $$ \sum_{k=1}^{2p+2} \frac{(-1)^{k+1}}{k} = \frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=1}^{2p} \frac{(-1)^{k+1}}{k} $$  The last term can now be exchanged for the RHS in the original equality:  $$\frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=1}^{2p} \frac{(-1)^{k+1}}{k} = \frac{(-1)^{2p+3}}{2p+2} + \frac{(-1)^{2p+2}}{2p+1} + \sum_{k=p+1}^{2p} \frac{1}{k}$$  Since $2p+3$ is odd and $2p+2$ is even, we get:  $$\frac{(-1)}{2p+2} + \frac{1}{2p+1} + \sum_{k=p+1}^{2p} \frac{1}{k} = \frac{(-1)}{2p+2} + \sum_{k=p+1}^{2p+1} \frac{1}{k}$$  ...because we can easily absorb the second term in the third term sum. However, I am stuck here because the first term is negative. I probably made a trivial error somewhere, but I am unable to find it. Any suggestions?
15046
I am looking for an example where you have $P(n)$ implying $P(n+1)$. However there is no base case. For which there is therefore no solution at all for the induction problem even though the inductive step itself works.
42494
Why does:   $$ \sum_{k=0}^{n} k \binom nk p^k (1-p)^{n-k} = np $$ ? Taking the derivative of:   $$ \sum_{k=0}^{n}  \binom nk p^k (1-p)^{n-k} = (1 + [1-P])^n = 1 $$   does not seem useful, since you would get zero. And induction hasn't yet worked for me, since – during the inductive step – I am unable to prove that:   $$ \sum_{k=0}^{n+1} k \binom {n+1}{k} p^k (1-p)^{n+1-k} = (n+1)p  $$   assuming that:   $$ \sum_{k=0}^{n} k \binom {n}{k} p^k (1-p)^{n-k} = np  $$
58589
I am trying to use mathematical induction to prove  $$(2n)!\ge2^n(n!)^2\quad\text{for }n\in\mathbb{N}$$  I am stuck at the $n=k+1$ point.
60101
Let $n \in \mathbb N^+$. Show that if $x_1, x_2, ... , x_n$ are $n$ real numbers such that $-1 \le x_i \le 0$ for each $1 \le i \le n$, then $$(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + x_1 + x_2 + ... + x_n$$  I am using a proof by induction, but I am unable to complete it. I would appreciate any tips on how I could finish the proof.   Incomplete Proof Let $P(n)$ be the proposition that $(1 + x_1)(1 + x_2)...(1 + x_n) \ge 1 + \sum_{i = 1} ^ n x_i$. When $n = 1$, LHS = RHS = $1 + x_i$. Clearly $1 + x_i \ge 1 + x_i$ and so $P(1)$ is true. Assume that $P(k)$ is true, i.e. $(1 + x_1)(1 + x_2)...(1 + x_k) \ge 1 + \sum_{i=1}^k x_i$. Case 1 Suppose $x_{k + 1}  = -1$. Then $1 + x_{k + 1} = 0$, hence LHS = $(1 + x_1)(1 + x_2)...(1 + x_k)(1 + x_{k+1}) = 0$. RHS = $1 + x_1 + x_2 + ... + x_k - 1 = x_1 + x_2 + ... + x_k$ which is always nonpositive since each $x_i$ is nonpositive. Hence RHS $\le 0$ and so LHS $\ge$ RHS. Case 2 Suppose $x_{k+1} = 0$. Then $1 + x_{k+1} = 1$, hence multiplying it to LHS does not change anything. Also, adding $x_{k+1}$ to RHS does not change anything. Therefore, LHS $\ge$ RHS still holds. Case 3 Suppose $-1 &lt; x_{k+1} &lt; 0$. Then $0 &lt; 1 + x_{k+1} &lt; 1$. Adding $x_{k+1}$ to RHS makes the RHS smaller since $x_{k+1}$ is negative. If LHS $= 0$, then multiplying $1 + x_{k+1}$ to LHS does not change anything, and so LHS $\ge$ RHS holds. If LHS > $0$, then multiplying $1 + x_{k+1}$ to LHS makes the LHS smaller since $0 &lt; 1 + x_{k+1} &lt; 1$. In this case LHS $\ge$ RHS does not necessarily hold? ...
122652
I need to prove $\sum\limits_{i=2}^{n}\frac{1}{(i-1)i}$ = $\frac{(n-1)}{n}$ using induction. I am getting stuck midway through the inductive step.   Here is what I have:  $\forall n\geq 2$, where $n\in\mathbb{N}, P(n)$ is the statement "$\sum\limits_{i=2}^{n}\frac{1}{(i-1)i}$ = $\frac{(n-1)}{n}$".  Base case:  $\sum\limits_{i=2}^{2}\frac{1}{(i-1)i}$ = $\frac{1}{2}$ = $\frac{(2-1)}{2}$ so $P(2)$ is true.  Inductive assumption: Assume $P(n)$ is true. Need to show $\sum\limits_{i=2}^{n+1}\frac{1}{(i-1)i}$ = $\frac{((n+1)-1)}{(n+1)}$.  $\sum\limits_{i=2}^{n}\frac{1}{(i-1)i}$ + $\frac{1}{n^{2}}$ = $\frac{(n-1)}{n}$ + $\frac{1}{n^{2}}$  = $\frac{n(n-1) + 1}{n^{2}}$ = $\frac{n^{2}-n+1}{n^{2}}$  I got stuck here and tried working backward from $\frac{((n+1)-1)}{(n+1)}$, which gives me:  $\frac{((n+1)-1)}{(n+1)}$ = $\frac{n}{(n+1)}$   Any suggestions on what to do next or where I may be going wrong?