Show that $$\frac1{1\cdot2}+\frac1{2\cdot3}+\frac1{3\cdot4}+\cdots+\frac1{(n-1)\cdot n}=\frac{n-1}{n}.$$   I’m having a really hard time with this question - I can’t start it with one because you can’t divide by zero, and as I go further along I still am struggling. I started with two, so I did the base step, and the induction hypothesis step, how do you prove that K+1 is true? How do I do this process and what’s the answer?
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?
18754
I just realized something interesting. At schools and universities you get taught mathematical induction. Usually you jump right into using it to prove something like   $$1+2+3+\cdots+n = \frac{n(n+1)}{2}$$  However.  I just realized that at no point is mathematical induction proved itself? What's the mathematical induction's proof? Is mathematical induction proved using mathematical induction itself? (That would be mind blowing.)
19547
Prove by Mathematical Induction . . .  $1(1!) + 2(2!) + \cdot \cdot \cdot +n(n!) = (n+1)!-1$  I tried solving it, but I got stuck near the end . . .  a. Basis Step:      $(1)(1!) = (1+1)!-1$      $1 = (2\cdot1)-1$      $1 = 1 \checkmark$   b. Inductive Hypothesis     $1(1!) + 2(2!) + \cdot \cdot \cdot +k(k!) = (k+1)!-1$   Prove k+1 is true.     $1(1!) + 2(2!) + \cdot \cdot \cdot +(k+1)(k+1)! = (k+2)!-1$      $\big[RHS\big]$      $(k+2)!-1 = (k+2)(k+1)k!-1$      $\big[LHS\big]$      $=\underbrace{1(1!) + 2(2!) + \cdot \cdot \cdot + k(k+1)!} + (k+1)(k+1)!$ (Explicit Last Step)      $= \underbrace{(k+1)!-1}+(k+1)(k+1)!$ (Inductive Hypothesis Substitution)      $= (k+1)!-1 + (k+1)(k+1)k!$      $= (k+1)k!-1 + (k+1)^{2}k!$   My [LHS] looks nothing like my [RHS] did I do something wrong?  EDIT:     $ = (k+1)k! + (k+1)^2k! -1 $      $ = (k+1)(k!)(1 + (k+1))-1$      $ = (k+1)(k!)(k+2)-1 = (k+2)(k+1)k!-1$
39985
Prove by induction:   $$\sum_{i=1}^{n} i \cdot 2^i = (n-1) \cdot 2^{n+1} +2$$   Basis: let $p(n)$ be the predicate.  Let $n=1$ this gives $(1-1) \cdot 2^1+1+2 = 2$ and $1 \cdot 2^1 = 2$ so its true for $p(1)$  Induction: assume $n=k$ thus $$\sum_{i=1}^{k} i \cdot 2^i = (k-1) \cdot 2^{k+1} +2$$  when $n=k+1$:  $$\sum_{i=1}^{k+1} i \cdot 2^i = \sum_{i=1}^{k} i \cdot 2^i + ((k+1)-1) \cdot 2^{(k+1)+1} +2$$  $$ =(k-1) \cdot 2^{k+1} +2 + ((k+1)-1) \cdot 2^{k+2} +2$$  $$= 2^{k+1}k - 2^{k+1} +2 +2^{k+2}(k+1) - 2^{k+2}+2$$  $$=\frac{2^{k+1}k-2^{k+1}+2 \cdot 2^{k+1}(k+1)-2 \cdot 2^{k+1} +4}{2}$$  $$=2^{k+1}k-2^{k+1}+2^{k+1}(k+1)-2^{k+1}+2$$  $$= (k-1) \cdot 2^{k+1}+((k+1)-1) \cdot 2^{k+1} +2$$  I've been messing around with the arithmetic part of this for a while now and it's getting frustrating, I'm thinking that I've possibly made a mistake at the beginning of the induction step and that's why I cant get this to work, or maybe I'm just missing something in the algebra, either way can someone please help.
97505
Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$  I have expanded it this far:  $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$  but then I am stuck from where to go from there.
16808
While thinking about  I found out that this equality might be useful there: $$n\cdot 1 + (n-1)\cdot 2 + \dots + 2\cdot (n-1) + 1\cdot n = \frac{n(n+1)(n+2)}6$$ To rewrite it in a more compact way: $$\sum_{k=1}^n k(n+1-k)=\frac{n(n+1)(n+2)}6.$$  This equality is relatively easy to prove: $$\sum_{k=1}^n k(n+1-k)= (n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 = (n+1) \frac{n(n+1)}2 - \frac{n(n+1)(2n+1)}6  = n(n+1) \left(\frac{n+1}2-\frac{2n+1}6\right) = n(n+1)\frac{3(n+1)-(2n+1)}6 =  \frac{n(n+1)(n+2)}6.$$ (We only used the known formulas for the   and the .)   Are there some other nice proofs of this equality? (Induction, combinatorial arguments, visual proofs, ...)     EDIT: Now I found another question which asks about the same identity:  (I have tried to search before posting. But the answers posted here so far gave me some new ideas for good keywords to search which lead me to finding that question.) The questions are, in my opinion, not exact duplicates since the other question asks specifically about combinatorial proofs and my question does not have that restriction. But I agree that this is a very minor distinction. In any case, if you think that one of them should be closed as a duplicate, then you can vote to close. I will refrain from voting to close/reopen on this question. (If one of the two questions is voted to be a duplicate of the other one, they probably cannot be merged, since the summation variables are off by one.)
5998
Proving $\frac{1}{n+1} + \frac{1}{n+2}+\cdots+\frac{1}{2n} &gt; \frac{13}{24}$ for $n&gt;1,n\in\Bbb N$  To solve it I used induction but it is leading me nowhere my attempt was as follows:  Lets assume the inequality is true for $n = k$ then we need to prove that it is true for $k+1$  so we need to prove $\frac1{k+2} + \frac1{k+3}+\cdots+\frac1{2(k+1)} &gt; 13/24$  I don't know where to go from here please help.
68740
This one should be pretty easy as its only a first year math problem. it s proof by induction that Im having trouble with.  $$let\;x_{1}=1; for\;each\;n\in \mathbb{N}\;let\;x_{n+1}=\frac{2}{3}x_{n}+1; prove\; x_{n}&lt; 3\;for\;all\;n$$  If anyone is willing to spell it out really obviously step by step and explain how they got from one step to the next I would appreciate it a lot. Thanks.
81465
Show that   $$(p-1)!\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{p-1}\right)\equiv 0\pmod{p^2}.$$   Maybe use this $$\dfrac{1}{k}+\dfrac{1}{p-k}=\dfrac{p}{k(p-k)}$$ and then I can't. Can you help me to prove it?   Thank you.
1706
I am having trouble with the following proof:     For every positive integer $n$: $$1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$$   My work: I have tried to add $\frac{1}{(k+1)^2}$ to $2-\frac{1}{k}$ in the inductive step and reduce it down to $2-\frac{1}{k+1}$ but cannot do so. I am beginning to think that my entire approach is wrong.
82765
My problem is how to prove  $$\frac{1+2}{1}  &gt; \frac{1+3+\frac{3^2}{2!}}{1+2} &gt; \frac{1+4+\frac{4^2}{2!}+\frac{4^3}{3!}}{1+3+\frac{3^2}{2!}}&gt;\cdots $$  i am sure that the sequence is decreasing as limit exp(1).  However, the reason why the sequence is decreasing is not evident.  Thanks if you consider this issue and make me relief.
80605
Prove    $$ \frac{1}{\sin 2x} + \frac{1}{\sin 4x } + \cdots + \frac{1 }{\sin 2^n x} = \cot x - \cot 2^n x $$   where $n \in \mathbb{N}$ and $x$ not a multiple of $\frac{ \pi }{2^k} $ for any $k \in \mathbb{N}$.   My try. If $n=2$, we have  $$\begin{align} \frac{1}{\sin 2x} + \frac{ 1}{\sin 4 x} &amp;= \frac{1}{\sin 2x} + \frac{1}{2 \sin 2x \cos 2x } \\[6pt] &amp;= \frac{ 2 \cos 2x + 1 }{2 \sin 2x \cos 2x} \\[6pt] &amp;= \frac{2 \cos^2 x - 2 \sin^2 x + \cos^2 x + \sin^2 x}{2 \sin 2x \cos 2x} \\[6pt] &amp;= \frac{3 \cos^2 x - \sin^2 x}{2 \sin 2x \cos 2x} \end{align}$$  but here I got stuck. I am on the right track? My goal is to ultimately use induction.
57680
$$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt n}\geq \sqrt n$$ I want to prove this by Induction  $$n=1 \checkmark\\ n=k \to \dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt k}\geq \sqrt k\\ n=k+1 \to \dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt {k+1}}\geq \sqrt {k+1}$$ so $$\dfrac{1}{\sqrt 1}+\dfrac{1}{\sqrt 2}+\dfrac{1}{\sqrt 3}+\cdots+\dfrac{1}{\sqrt k}+\dfrac{1}{\sqrt {k+1}}\geq \sqrt k+\dfrac{1}{\sqrt {k+1}}$$now we prove that $$\sqrt k+\dfrac{1}{\sqrt {k+1}} &gt;\sqrt{k+1} \\\sqrt{k(k+1)}+1 \geq k+1 \\ k(k+1) \geq k^2 \\k+1 \geq k \checkmark$$ and the second method like below ,   and I want to know is there more Idia to show this proof  ? forexample  combinatorics proofs  , or using integrals ,or fourier series ,....    Is there a close form for this summation ?  any help will be appreciated .
36572
I would like to show that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}$ holds for all natural numbers. I got stuck here:  $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\cdot\frac{2n+1}{2n+2}\leq \frac{1}{\sqrt{3n+1}}\frac{2n+1}{2n+2}.$  I would appreciate your help.
10195
If $a, b, c \in \mathbb{N}$, and $abc = 1$, prove that: $$S = \frac{2}{(a+1)^2+b^2+1} + \frac{2}{(b+1)^2+c^2+1} + \frac{2}{(c+1)^2+a^2+1} \le 1$$  Here is my try: $$\begin{align}\frac{2}{(a+1)^2+(b^2+1)} &amp; \le \frac{1}{\sqrt{(a+1)^2 \cdot (b^2+1)}}\\ &amp; = \frac{1}{(a+1) \cdot \sqrt{b^2+1}}\\ &amp; \le \frac{1}{(a+1) \cdot b}\\ &amp; \le \frac{1}{ab} \end{align}$$  So, $$S \le \frac{1}{ab} + \frac{1}{bc} + \frac{1}{ca} = \frac{a+b+c}{1}$$  Can you help me to continue it, please? Thanks!
36259
Prove that $2^{2\cdot 3^{n-1}}\equiv 1+3^n\pmod{3^{n+1}}$ for every natural $n$   Of course, should be done by induction. Base case ($n=1$) is easy.  I got stuck with the step:  Let's assume that it's right for $n$. Then,  $$2^{2\cdot 3^{n-1}} = 1 + 3^n \pmod{3^{n+1}}$$  We want to evaluate $$2^{2 \cdot 3^n} \pmod {3^{n+2}}$$  I think we can somehow utilize the fact that $2,3$ are coprime and reduce $3^{n+2}$ to $3^{n+1}$.   I'd be glad for help on that.  Thanks!
44373
I am wondering how to prove both of this by induction: $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{2^n}\leq 1+\frac{n}{2}$ In general, how should I think of how to prove such an inductive step for these types of inequalities? If there is any other way to prove please feel free. Any help would be appreciated.