0
votes
3answers
42 views

Finding the Formula For the Sum of a Sequence

In the problem below, It is asked to find the formula for the sum of the sequence and then to prove whether it is true or false for all n values using induction. $$ 1 + 4 + 7 + ... + (3n + 1), \ n\in ...
1
vote
1answer
28 views

Discrete Math Induction: $\sum^n_{i=1} \frac1{i(i+1)}$ [duplicate]

For $\sum^n_{i=1} \frac1{i(i+1)}$ Find a formula and proofs that it holds for all n ≥ 1. How would I find the formula for this one that can hold for all n ≥ 1?
-1
votes
2answers
42 views

Discrete Math On Induction proof: $\sum_{i=1}^n n2^n = (n-1)2^{n+1} + 2$ [duplicate]

Show by induction that the following formulas hold. $\sum_{i=1}^n n2ⁿ = (n-1)2^{n+1} + 2$ What did a similar problem to this but this one is a little different. I think is because this one has a ...
-1
votes
1answer
86 views

Use Mathematical Induction to prove that $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} +…+\frac{1}{n(n+1)}=1-\frac{1}{n+1}$

Use Mathematical induction to prove that for all integers, $n$ is greater than or equal to $1$. I am confused on what to do after I do the the basis step that is using $n$ as $1$. $$\frac{1}{1 \cdot ...
0
votes
2answers
41 views

Inductive proof and summation

The problem asks me to prove by induction that: $$\sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4}$$ I've worked through it at least half a dozen times, checked my math fastidiously, can't seem to figure it ...
0
votes
3answers
31 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
1
vote
1answer
82 views

Can't find an identy for proving that $ \sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$ \sum_{k=0}^{i+1} \binom {i+1} k$$ I can't find an identity for this summation :( To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and ...
3
votes
2answers
53 views

Help finishing proof via induction for a summation

So I have to prove the following equation using induction for n >= 2: $$ \sum\limits_{i=1}^n 4/5^i < 1 $$ However the question asks me to prove something stronger such as this: $$ ...
0
votes
1answer
24 views

Using induction to prove $\sum\limits^n_{k=1} 9^k = 0.5 \cdot \sum\limits^{2n}_{k=1} (-1)^k \cdot 3^{k+1}$

$$\sum^n_{k=1} 9^k = 0.5 \cdot \left[\sum^{2n}_{k=1} (-1)^k \cdot 3^{k+1}\right]$$ I have tested both with a python script and it seems to be correct. For the life of me, I am unable to unwind the ...
1
vote
2answers
37 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
1
vote
2answers
49 views

How can I come up with a formula for this summation?

I have to come up with a formula for: $$\sum_{0\le i\le n\text{, i is even}}^\ i^2$$ and then prove it by using induction. I know how to do the proof, but I am stuck on coming up with the formula. I ...
2
votes
4answers
138 views

Mathematical Induction (summation)

I am stuck on this question from the IB Cambridge HL math text book about Mathematical induction. I am sorry about the bad formatting I am new and have no idea how to write the summation sign. Using ...
3
votes
2answers
145 views

Induction: show that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$

The question: show by using induction that $\sum\limits_{k=1}^n \frac{1}{\sqrt{k}} < 2 \sqrt{n}$ for all n $\in Z_+$ My attempt at a solution: The base case $n = 1$ is true. First we use the ...
1
vote
2answers
120 views

Show $\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$

My question is: show $$\sum_{k=0}^{m} \binom{n-k}{m-k}=\binom{n+1}{m}$$ $$n\geq m\geq 1$$ I tried to do this via induction and failed. there has to be another way of doing this. We could either ...
2
votes
2answers
150 views

Use induction and Newton's binomial formula to show that $\binom{n}{0}+\binom{n}{1}+\cdot+\binom{n}{n}=2^n, \forall n\in \mathbb N$ [duplicate]

Use induction and Newton's binomial formula to show that: $ i)$ $ \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n, \forall n\in \mathbb N$ $ ii)$ ...
2
votes
6answers
174 views

Certain step in the induction proof $\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ unclear

It's about proving the following: $$\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$ I understand every step in the master solution, however, I have no idea how one can know by intuition to ...
0
votes
1answer
83 views

Binomial coefficients identity (sum of the powers of the natural numbers)

I've found exercise with binomial coefficients in Kostrikin's book. Proof that $\sum_{i=1}^n{{r+1}\choose{i}}\left(1^i+2^i+\dots+n^i\right)=(n+1)^{r+1}-(n+1)$ I was trying to check that for ...
3
votes
3answers
169 views

Given n $\in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
3
votes
2answers
77 views

Prove that $\sum_{k=0}^n\frac{1}{k!}\geq \left(1+\frac{1}{n}\right)^n$ [duplicate]

It basically says it all in the title. I tried solving the inequality using the bernoulli inequality somehow $$\dfrac{\displaystyle\sum_{k=0}^n\frac{1}{k!}}{(1+\frac{1}{n})^n}\geq 1,$$ but the ...
1
vote
1answer
110 views

Prove a summation inequality by induction

I was having trouble proving by induction with this problem. $$\sum_{i=1}^n \frac{3}{4^i} < 1$$ for all $n \geq 2$ I went to see my professor and he said try proving this equality ...
2
votes
4answers
121 views

Prove that $1+a+a^2+\cdots+a^n=(1-a^{n+1})/(1-a)$.

I have problem. Prove this using Mathematical Induction. I am a newbie in Mathematics. Please help me. $$1+a+a^2+\cdots+a^n = \frac{1-a^{n+1}}{1-a}$$ This is my way for get the proof Basic ...
2
votes
3answers
69 views

How do you solve a recurrence with a summation function inside

Show that $$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$ is the same as $$t(n) = 2^n$$ Initial condition $t(0) = 1$
4
votes
2answers
77 views

Prove by mathematical induction that $\sum_{i=1}^{n}\frac{i}{2^i}\leq2$ for $n\ge 1$

I have this exercise by my professor that I have no idea how to solve. Any help would be greatly appreciated: Using the method of mathematical induction show that for all $n \geq 1$, $n ...
0
votes
2answers
51 views

Prove $\sum_{i=1}^{n}i\left(\begin{array}{c} n\\ i \end{array}\right)=n2^{n-1}$ using induction.

I have already derived the formula $\sum_{i=1}^{n}i\left(\begin{array}{c}n\\i \end{array}\right)=n2^{n-1}$ directly just by doing some algebraic manipulations to the summand, which is indeed proves ...
1
vote
2answers
82 views

How do I prove $2^{n+1} + 2n + 1 = 2^{n+2} - 1$

I am attempting to prove using induction: $\sum_0^n 2i = 2^{n + 1} - 1$ I have gotten to the point where I need to show: $2^{n+1} + 2n + 1 = 2^{n+2} - 1$ How do I prove this? Or should I be ...
0
votes
1answer
65 views

Proof by induction that $1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ [duplicate]

How would I go about solving this question? Use induction to prove that for all integers $n ≥ 1$, $$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$$
0
votes
1answer
59 views

Inequality with a sum and factorial

For a homework assignment we have the following question that I'm stuck on. Let $ 0 \leq y \leq 1 $ be given. $\forall m \in \mathbb{N}$, define $ \displaystyle S_m(y)=\sum_{k=0}^m \binom{m}{k}y^k$. ...
0
votes
3answers
365 views

Induction step for $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

I want to prove by induction that, $\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$ OK I got the initial step, however, I have problems with the induction step: Here is what I tried: ...
2
votes
2answers
143 views

Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$

everyone. I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states: $$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$. I ...
1
vote
1answer
87 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
1
vote
1answer
45 views

Inductive demonstration

I have this: $$1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}6$$ So I was suggested of doing this: $$\begin{align} (1^2+2^2+3^2+\dots+k^2)+(k+1)^2 &= \frac{k(k+1)(2k+1)}6+(k+1)^2 \\ &= ...
1
vote
3answers
357 views

Summation and proof by induction question

I can't figure this out based on examples in textbooks, etc. Show via induction that $\sum_{j=1}^{n}j(j+1)(j+2)=\frac{n(n+1)(n+2)(n+3)}{4}$ So far, I have: (a) base case $P(1)= 1(1+1)(1+2) = ...
0
votes
2answers
283 views

How to proof linearity property of summations with induction

Recently I have faced with this question: $ {\sum_{k=1}^{n} (ca_k+ b_k) = c \sum_{k=1}^{n} a_k + \sum_{k=1}^{n} b_k }$ Proof linearity property of summations for all n ≥ 0 by using mathematical ...
2
votes
3answers
509 views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...
1
vote
3answers
103 views

Proving $\sum_{k=1}^nk^3 = \left(\sum_{k=1}^n k\right)^2$ using complete induction [duplicate]

I tried to prove the following statement using complete induction but I couldn't manage to solve it because I got a complex notation eventually. The statement is the following: $$\sum_{k=1}^nk^3 = ...
4
votes
3answers
362 views

induction proof: $\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$

I encountered the following induction proof on a practice exam for calculus: $$\sum_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$$ I have to prove this statement with induction. Can anyone please help me ...
0
votes
1answer
79 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
4
votes
6answers
96 views

Is $\sum_{i=1}^{n-1}i=\binom{n}{2}$?

How can I show that $$ \sum_{i=1}^{n-1}i=\binom{n}{2}? $$ This is what I have tried, but I do not know if it is correct: Proof. Let $n=2$. Then, $$ \begin{align} \sum_{i=1}^{1}i&=1\text{, ...
1
vote
2answers
84 views

Prove by induction that $1^3 + 2^3 + 3^3 + …+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. [duplicate]

Use mathematical induction to prove that $1^3 + 2^3 + 3^3 + .....+ n^3= \frac{n^2(n+1)^2}{4}$ for all $n\geq1$. Can anyone explain? Because I have no clue where to begin. I mean, I can show that ...
2
votes
3answers
80 views

Problem with Proof of Inequality with Squares by Induction

I am a bit new to logical induction, so I apologize if this question is a bit basic. I tried proving this by induction: $$\left(\sum_{k=1}^nk\right)^2\ge\sum_{k=1}^nk^2$$ Starting with the base ...
1
vote
3answers
82 views

Using induction to verify a statement

I have to prove that this statement is true. For $n = 1, 2, 3, ...,$ we have $ 1² + 2² + 3² + ... + n² = n(n + 1)(2n + 1)/6$ Basically I thought I'd use induction to prove this. Setting $n = p+1$, I ...
9
votes
2answers
148 views

Proving that $\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$

How do I prove that: $$\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots+\frac{1}{\sqrt{100}}<20$$ Do I use induction?
0
votes
2answers
120 views

I need help with proofs using mathematical Induction

I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
6
votes
4answers
191 views

Sum of the first $n$ triangular numbers - induction

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 ...
3
votes
3answers
258 views

Induction proof of $\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$

Does anynone have some hints to prove the following equation by induction for all $n\geq 1$ and $m\in\mathbb{Z} $ $$\sum_{j=0}^n{(-1)^j{n \choose j}\prod_{k=m+1}^{m+n-1}{(j+k)}}=0$$ use for ...
2
votes
3answers
100 views

How would you prove $\sum_{i=1}^{n} (3/4^i) < 1$ by induction?

How would you prove this by induction? $\sum_{i=1}^{n} (3/4^i) < 1$, $ \forall n \geq 2$ I can do the base case but dont know how to to finish it
4
votes
2answers
87 views

$\sum_{i=1}^n i\cdot i! = (n+1)!-1$ By Induction

I am trying to prove the following by Mathematical Induction: $$\sum_{i=1}^n i\cdot i! = (n+1)!-1\quad\text{for all integers $n\ge 1$}$$ My proof by Induction follows: First prove $P(1)$ is true, ...
5
votes
2answers
2k views

Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$

I would like to prove inductively that $${2n\choose n}=\sum_{i=0}^n{n\choose i}^2.$$ I know a couple of non-inductive proofs, but I can't do it this way. The inductive step eludes me. I tried naively ...
3
votes
4answers
64 views

How to prove $\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}$? [duplicate]

How can I prove that $\sum^n_{i=1} \frac{1}{i(i+1)} = \frac{n}{n+1}$? I noticed that in the sum, the denominator has terms that cancel out, but I'm not sure how to take advantage of that.
5
votes
3answers
694 views

Complete induction

I am very confused with complete induction. Because in every task there is something different to do, and I never know what to insert (thats my biggest problem). Here's the example: Proof with ...