Prove by induction (weak or strong) that:    $$\sum_{k=0}^{n-1}(k + 1)^2= \frac{n(n + 1)(2n+1)}{6}$$  My base case is:    $n = 1$, which is true.  In my Inductive Step, I assume that: $$S(n)=\frac{n(n + 1)(2n+1)}{6}$$ holds for an arbitrary value of $n$.    Proving it then holds for $n+1$: $$ S(n+1)=\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}$$ $$ \phantom{S(n+1)}=\frac{(n+1)((n+2)(2n+2+1)}{6}$$ $$ \phantom{S(n+1)}=\frac{(n+1)((n+2)(2n+3)}{6}$$ $$ \phantom{S(n+1)}=\frac{2n^3+9n^2+13n+6}{6}$$  but can't see how my definition of $S(n)$ can be substituted into this final equation?  [EDIT] This isn’t a duplicate because the original summation of $(k+1)^2$ is what I’m originally provided with. The apparent duplicate question also doesn’t have a correct proof by induction answer associated with it.
6333
I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:  $$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$  I really have no idea why this statement is true. Can someone please explain why this is true and if possible show how to arrive at one given the other?
72107
For $n \geq 2$ prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$  We need to use induction.   The Principle of Mathematical Induction, Theorem 4.2.1, states that $n_0 \in \mathbb{Z}$. For each integer $n \geq n_o$, let $P(n)$ be a statement about $n$. Suppose that the following two statements are true:   $P(n_o)$ $( \forall n \geq n_o)[P(n) \rightarrow P(n+1)]$   Then, for all integers $n \geq n_o$, that statement $P(n)$ is true.  Suppose,  $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$, the equation, is true for some natural number $k$.  $\frac{1}{2^2})*...*(1- \frac{1}{k^2}) = \frac{k+1}{2k}$  The induction hypothesis $P(k) \rightarrow P(k+1)$ must hold for any natural number $k, P(k),$ from the basis and inductive step.  $(\frac{1}{2^2})*...*(1- \frac{1}{k^2})*(1- \frac{1}{(k+1)^2}) = \frac{k+1}{2k}(1- \frac{1}{(k+1)^2})$  $\leftrightarrow$ $\frac{k+1}{2k}(\frac{(k+1)^2}{(k+1)^2}- \frac{1}{(k+1)^2})$  $\leftrightarrow$ $(\frac{(k+1)}{2k})( \frac{(k+1)^2-1}{(k+1)^2})$  $\leftrightarrow$ $( \frac{(k^2+2k+1-1}{(2k)(k+1)})$  $\leftrightarrow$ $( \frac{(k^2+2k}{(2k)(k+1)})$  $\leftrightarrow$ $( \frac{k+2}{(2)(k+1)})$  We need to demonstrate that   $(\frac{1}{2^2})*...*(1- \frac{1}{n^2}) = \frac{n+1}{2n}$  holds true for $n \geq 2$  The question is do I just substitute a number that is greater than two after I did the induction?
54720
Mathematica tells me that  $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$  Although I have not been able to come up with a proof.  Proofs, hints, or references are all welcome.
15333
How to prove that $ 2&lt;(1+\frac{1}{n})^{n}$ for every integer $n&gt;1$. I was thinking by induction, it works for $n=2$ but then I couldn't move forward.
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!
52877
So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so here I am. Thanks in advance.
16144
I am trying to prove the summation formula using induction:  $$\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$$  So far I have...  Base case:   Let n=1 and test   $\frac{1}{k(k+1)} = 1-\frac{1}{n+1}$  $\frac{1}{1(1+1)} = 1-\frac{1}{1+1}$    $\frac{1}{2} = \frac{1}{2}$   True for n=1   Induction Hypothesis:   Assume the statement is true for the n-th case   $\sum_{k=1}^n  \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$  Inductive Step:   Prove, using the Inductive Hypothesis as a premise, that   $$\sum_{k=1}^{n+1}  \frac{1}{k(k+1)} = \sum_{k=1}^{n}  \frac{1}{k(k+1)} + \frac{1}{(n+1)(n+2)} = 1-\frac1{n+1} + \frac{1}{(n+1)(n+2)} = \frac{(n+1)(n+2)}{(n+1)(n+2)}+\frac{-2-n}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)} = \frac{(n+1)(n+2)-2-n+1)}{(n+1)(n+2)} = \frac{(n+1)(n+2)-n-1}{(n+1)(n+2)} = \frac{n^2+2n+1}{(n+1)(n+2)} = \frac{(n+1)(n+1)}{(n+1)(n+2)} = \frac{n+1}{n+2}$$  To prove $$ 1-\frac{1}{n+2} = \frac{n+1}{n+2} $$ Multiply both sides by $n+2$ to get an equivalent expression. $$ (1-\frac{1}{n+2}) * (n+2) = (\frac{n+1}{n+2}) * (n+2)  $$ $$ n+1=n+2−1 $$  Does this all make sense? How can this be improved upon?
114112
Let $S_k(n)$, for $k = 0, 1, 2, \ldots$, be defined as follows  $$S_k(n) = \sum_{i=1}^n \ i^k$$  For fixed (small) $k$, you can determine a nice formula in terms of $n$ for this, which you can then prove using e.g. induction. For small $k$ we for example get  $$\begin{align} S_0(n) &amp;= n\\ S_1(n) &amp;= \frac{1}{2}n^2 + \frac{1}{2}n \\ S_2(n) &amp;= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n \\ S_3(n) &amp;= \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2 \\ S_4(n) &amp;= \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n \end{align}$$  The coefficients of these polynomials are related to the Bernoulli-numbers, and getting arbitrary coefficients in these polynomials (i.e. the coefficient of $n^m$ in $S_k(n)$ for large $k,m$) is not so easy. However, th first two coefficients follow a simple pattern: the coefficient of $n^{k+1}$ is $\frac{1}{k+1}$ and the coefficient of $n^k$ (for $k > 0$) is always $\frac{1}{2}$. My main question now is:      How can we prove that $S_k(n) = \frac{1}{k+1}n^{k+1} + \frac{1}{2}n^k + O(n^{k-1})$ for $k &gt; 0$?   The first coefficient can be explained intuitively, as  $$S_k(n) = \sum_{i=1}^n \ i^k \approx \int_{i=1}^n i^k di \approx \frac{n^{k+1}}{k+1}$$  Maybe you could make this more rigorous, but I don't see how you will get the term $\frac{1}{2}n^k$ with this.  Also, while the coefficient of $n^{k+1}$ can be explained intuitively, it's not clear to me why the coefficient of $n^k$ is $\frac{1}{2}$, and why this one is fixed while e.g. the coefficient of $n^{k-1}$ is different for different $k$. If someone could explain that, that would be appreciated as well.  Thanks.
118808
Question:  Prove by mathematical induction that $$(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)=\frac{1}{6}n(n+1)(n+2)$$ is true for all positive integers n.  Attempt:  I did the the induction steps and I got up to here: $$RTP:\frac{1}{6}n(n+1)(n+2)+(1+2+3+\cdots+n+(n+1))=\frac{1}{6}(n+1)(n+2)(n+3)$$ Where do I go from here?  Thank you very much.
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?
120175
I want to justificate following equation:  $$\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!}\frac{1}{2k+1} = \frac{2^n}{(2n+1)!!}$$  I calculated the both sides for $n$ from 1 to 10 and it was true. How the mathematical induction can be applied to this equation? Or is there other way to justificate it?
23389
Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.  As a hint I got that $k {n \choose k} = n {n-1\choose k-1} $.  I tried solving this by induction but, in the inductive step I'm not arriving to the correct result.
25555
I'm finding a closed form to  $\sum^{n}_{k=1} \frac{k}{(k+1)!}  (n \leq 1) $ (in a environment of induction and recurrence)   I've been trying to solve it without success, can anybody help me (?)  The last thing I've tried to do is write the expression as a Non-Homogeneous Linear Recurrence:   $ f(1) = \frac{1}{2} $   but, actually I have no idea of how to attach it.   $ f(n+1) = f(n) + \frac{1}{(n+2)n!} $
91788
Prove that for all $n \ge 1$:  $$\sum_{k=1}^n \frac{1}{k(k+1)} = \frac{n}{n+1}$$  What I have done currently:  Proved that theorem holds for the base case where n=1.  Then:  Assume that $P(n)$ is true. Now to prove that $P(n+1)$ is true:  $$\sum_{k=1}^{n+1} \frac{1}{k(k+1)} = \frac{n}{n+1} + n+1$$  So: $$\sum_{k=1}^{n+1} \frac{1}{k(k+1)} = \frac{n+1}{n+2}$$  However, how do I proceed from here?
9
I am stuck with the identity  $$ F_{2n} = \sum_{k=1}^n \binom{n}{k} F_k, $$  which happens to be formula . I am using induction, but so far without too much result.  $$ \sum_{k=1}^{n+1} \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n+1}{k} F_k = \\ F_{n+1} + \sum_{k=1}^n \binom{n}{k} F_k + \sum_{k=1}^n \binom{n}{k-1}F_k =\\ F_{n+1} + F_{2n} + \sum_{k=1}^n \binom{n}{k-1}F_k, $$   I am stuck with the sum $ \sum_{k=1}^n \binom{n}{k-1}F_k$, because, on the other hand   $$ F_{n+1}+ \sum_{k=1}^n \binom{n}{k-1}F_k = F_{2n+1} $$  Which would conclude the proof. What am I missing?
32786
$$\sum_{k=1}^nk(k!)$$  I know the answer is (n+1)!-1..I can solve this question using principle of mathematical induction...but I would like to know if there is any other alternative approach
100263
I'm trying to show that      $$\sum_{k=0}^n (-1)^k\frac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}} = \frac{x}{x+n}$$   I've tried expanding this using definition of binomial coefficient, then binomial expansion, now I'm using induction to simplify $\sum_{k=0}^m (-1)^k\frac{{ {n}\choose{k}}}{{ {x+k}\choose{k}}}$, but it looks very inelegant, is there a better way?