1
vote
2answers
91 views

Proof that $\dfrac{1}{e^x}=e^{-x}$ without converting it to $e^{x}e^{-x}=1$.

I want to show that $\dfrac{1}{e^x} = e^{-x}$ from the Taylor expansion of $e^x$. To express $\dfrac{1}{e^x}$ as a power series, I let: $$ \left(\dfrac{1}{0!}x^0 + \dfrac{1}{1!}x^1 + ...
3
votes
2answers
69 views

Limit of a sequence of averages (three variables)

Let $a_0 = 0$, $a_1 = 0$, $a_2=1$ and for $n>2$, $a_n = \dfrac{a_{n-1}+a_{n-2}+a_{n-3}}{3}$. Consider $\lim\limits_{n \to +\infty} a_n$. Using a python script I found that $a_n$ tends to ...
0
votes
1answer
32 views

how to prove using induction that sum of terms?

Prove that $\displaystyle\sum\limits_{i=1}^{k}\left(\dfrac{1}{(2i-1)}\dfrac{1}{(2i+1)}\right) = \dfrac{k}{(2k+1)}‎‎$ My Base of Induction is to check that it is true for i=1, so: ...
0
votes
2answers
37 views

How to use the Comparison Test to investigate the convergence of $\sum (\ln n)/n^\alpha$?

Let $$\sum\limits_{n=1}^\infty \frac{\ln n}{n^\alpha}, \alpha\in\Bbb{R}$$ I need to investigate the convergence of this series. I've read that since the series is positive for all $n$ then it ...
1
vote
0answers
38 views

A sequence defined as $a(n)=n-a(a(n-1))$ $n\geq 1,\ a(0)=0$, how to prove that $a(n)=⌊(n+1)(-1+√5)/2⌋$

$a(n)=n-a(a(n-1)), \ n \geq 1,\ a(0)=0$, to prove that $$ a(n)=⌊(n+1)\cdot \frac{\sqrt{5} - 1}{2}⌋. $$ This is an exercise of "Discrete Mathematics and Its Application".(Supplementary exercise 72 of ...
3
votes
4answers
64 views

Elementary Proof of sum of alternating factorials

so I came across the rather interesting identity $$ \sum_{i = 0}^{\infty}\left[\sum_{j=0}^{i}\left[\frac{(-1)^j}{j!} \right] \prod_{j=0}^{i}\left[ (x-j)\right] \right] = x! $$ For positive integers ...
1
vote
1answer
32 views

Sum of nth powers and generalized polynomial sum

So this is a 2-part question (both parts I believe are closely related): How exactly does on express the sum $$\sum_{i=0}^{k}{i^n} = Q(n,k)$$ in a closed form For arbitrary positive integers ...
2
votes
2answers
25 views

Proving arithmetic series by induction

How do I prove this statement by the method of induction: $$ \sum_{r=1}^n [d + (r - 1)d] = \frac{n}{2}[2a + (n - 1)d] $$ I know that $d + (r - 1)d$ stands for $u_n$ in an arithmetic series, and the ...
3
votes
2answers
87 views

Prove by induction that $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ is decreasing

I want to prove that the following sequence is monotonously decreasing: $A_k = \sum\limits_{n=2k}^{3k}\binom{3k}{n}\cdot{(\frac{60}{100})}^n\cdot{(\frac{40}{100})}^{3k-n}$ I think it should be ...
0
votes
1answer
42 views

a finite induction question from burton's elementary number theory

this question comes from burton's elementary number theory, 4th edition. question 3 in 1.1 says to use the second principle of finite induction to establish that $$for\ all\ n\ge1,\ ^{(a)}\ ...
3
votes
1answer
53 views

Do I need to use induction to have sufficient rigor in this proof?

I'm taking my first analysis class this summer. The professor asked us to prove that $a^{2n}-b^{2n}$ is divisible by $a+b$. After dorking around with the first couple of $n$ I was able to come up ...
0
votes
1answer
46 views

Find count of all combination of numbers whose sum is x

I want to find the sum of all combination of numbers whose sum is x, for e.g. when x = 3 f(x) = countOf(111,12,21,3) = 4
0
votes
1answer
31 views

Recursive sequence problem

$$U(n+1) = (6+U(n))^{1/3},\text{ and } U(0) = 1.$$ Prove by induction that for all positive integers $n, U(n)$ is increasing. Prove by induction that for all positive integers $n, U(n) \leq 2$ ...
-1
votes
3answers
58 views

How to prove that for any $n$ in $\mathbb{N}$ that $(\frac{3}{2})^n \ge n$?

Well, I was trying to do that using proof by induction and my attempt is : Base case : $(\frac{3}{2})^0 \ge 0$, true Assumption : $(\frac{3}{2})^k \ge k$. I've multiplied both sides by $(\frac{3}{2})$ ...
3
votes
3answers
119 views

Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ [duplicate]

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = ...
0
votes
1answer
74 views

Proving an inequality for a sequence by induction

I'm having some trouble with the following problem: Let $a_n$ be a sequence defined iteratively for $n \geq 0$ as follows: $a_n = a_{m+1} + 2a_m + a_{n-m-1} + 2$ where $m$ is defined as ...
-2
votes
1answer
34 views

How to prove this using induction?

The problem is : Using induction, prove that $ (\frac{n+1}{n})^n \le n $ for $ n>3 $ and then using that prove that the sequence $ 1 , 2 ^ {(1/2)}, 3 ^ {1/3},4^{1/4} .. $ is decreasing starting ...
0
votes
2answers
41 views

Proof for a theorem using induction

I have to prove the following using mathematical induction: $ S(n)= \frac{1}{3}+ \frac{1}{9}+...+ \frac{1}{3 ^{n-1} }+ \frac{1}{ 3^{n} } = 0.5 - \frac{1}{2*3^{n} } $ I understand I have to do the ...
1
vote
1answer
33 views

Is it obvious that $\sum_n x_n = 0 $ when $x_n = 0 ~ \forall n \in \mathbb N$?

Until recently I used to think that because of induction, a statement $P_n$ which is true $\forall n \in \mathbb N$ was also true when $n \to \infty$. Life was simple, and I was happy. Then someone ...
2
votes
2answers
61 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
1
vote
2answers
82 views

proof by maths induction

not sure how to prove this: for all positive intergers prove: \begin{equation} 1+2(2)+3(2^2)+...+n(2^{n-1})=(n-1)(2^n)+1 \end{equation} heres my try: prove $n=1$ : \begin{equation} 1=1 ...
1
vote
1answer
72 views

Prove any $k\in\mathbb{N}$ can be created using sum of $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$

I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition. My attempt was just bad... I've ...
1
vote
1answer
57 views

How do I solve this?

Define ${[X_n]}$ by: $X_n = 3, X_{n+1} = {\frac 12} (X_{n-1} + {2\over X_{n-1}})$ a) Show that for any n≥1 we have $X_n$≥ $\sqrt{2}$ b) Show that {$X_n$} is decreasing. c) Deduce from (a) and (b) ...
1
vote
2answers
66 views

Show by induction $|a_1-a_2+a_3-\ldots \pm a_n| \leq |a_1|$

The assumptions are that $(a_n)$ is a decreasing sequence with $(a_n) \to 0 $, that is all terms are nonnegative. It is easy to see that the subtracted terms are always at least as great as the added ...
0
votes
1answer
52 views

Proof By Induction Quest.

Prove that for all integers $n$ greater then $1$: $$ 1+\frac {1}{4} +\frac {1}{9} +\cdots+\frac {1}{n^2} <2-\frac{1}{n} $$ First verify that $p(n)$ is true for $n = 2$ $\frac { 1 }{ 4 } ...
1
vote
2answers
161 views

How to prove, by induction, that an infinitely nested radical is increasing

How do I prove using induction that an infinitely nested radical, like sqrt(1+sqrt(1+sqrt(1+... is increasing. I have seen there are many examples on here like this but haven't seen one that proves ...
-1
votes
1answer
60 views

Induction On $a_{n+1}$ Sequence

We define a sequence of rational numbers $\{a_n\}$ by putting $a_1=2$ and $$a_{n+1}=3−\frac1{a_n}$$ for all $n\in\Bbb N$. Put $$\alpha=\frac{3+\sqrt5}2\;.$$ I've shown that ...
1
vote
1answer
134 views

prove that sequence given by the recursion is monotonically increasing i mean $a_n\le a_{n+1}$

$a _{1} = \frac{1}{2}, a _{2} = 1, a _{n}= \frac{1}{2} a_{n-1} + \sqrt{a _{n-2} }$ Show by the induction that it's $\le$4 and also by the induction that $a_{n+1}-a_n \ge 0$ If it comes to first i ...
2
votes
4answers
121 views

Recurrence sequence limit

I would like to find the limit of $$ \begin{cases} a_1=\dfrac3{4} ,\, & \\ a_{n+1}=a_{n}\dfrac{n^2+2n}{n^2+2n+1}, & n \ge 1 \end{cases} $$ I tried to use this - $\lim ...
0
votes
2answers
44 views

Fibonacci Recursion Equation

For the Fibonacci sequence, prove the formula $a^2_{n+1} = a_n a_{n+2} + (-1)^n$ using induction. I have done the base case, when $n=3$, because for the Fibonacci sequence, $a_1=a_2=1$. I have no ...
3
votes
3answers
94 views

Can $(1-\frac{1}{2})(1-\frac{1}{2^2})(1-\frac{1}{2^3})…(1-\frac{1}{2^{n-1}})(\frac{1}{2^n})$ be simplified?

Can $(1-\frac{1}{2})(1-\frac{1}{2^2})(1-\frac{1}{2^3})...(1-\frac{1}{2^{n-1}})(\frac{1}{2^n})$ be simplified? It seems like an expression from a simple induction proof problem that's missing its ...
3
votes
3answers
78 views

How to prove the inequality $\sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2} $ for $n\in\mathbb{Z}^+$?

I have to prove this inequality: $$ \forall n \in Z^+, \sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2} $$ So far, I have done the base cases and assumed the inequality is true for some ...
0
votes
2answers
88 views

How to prove that a series is equal to a recursive algorithm

I have the following sequence: $$ y_n = \int_0^1 \frac{x^n}{x+5}\,dx, n = 0,1,\dots $$ Now I have the following recursive algorithm: $$ y_0 = \log{6} - \log{5} $$ $$ y_n = \frac{1}{n} - 5y_{n-1}, n ...
4
votes
2answers
81 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 ...
2
votes
4answers
3k views

Help with Induction proof on Fibonacci sequence?

I can't seem to solve this problem. It is: The Fibonacci numbers $F(0), F(1), F(2),\dots $ are defined as follows: $F(0) ::= 0$ $F(1) ::= 1$ $F(n) ::= F(n-1) + F(n-2)\qquad(\forall n \ge 2 $) ...
3
votes
2answers
276 views

Prove $\frac{1}{2} + \cos(x) + \cos(2x) + \dots+ \cos(nx) = \frac{\sin(n+\frac{1}{2})x}{2\sin(\frac{1}{2}x)}$ for $x \neq 0, \pm 2\pi, \pm 4\pi,\dots$

I know that this can be proven inductively. However, I can't get passed the trig. I am pretty sure trig identities can show that the expression above is true for $n=0$, and that if the expression ...
1
vote
3answers
84 views

How to do this Math induction problem?

Show that: $$\frac n3 + \frac n9 + \frac {n}{27} + \cdots = \frac n2.$$ When I start with $\frac 13 + \frac 19 + \frac {1}{27}$ it leads to a number close to $.5$ but it's not exactly $.5$.
0
votes
1answer
62 views

Induction proof with no terms of sequence

The sequence $[x_n]$ is given by $x_1=1$ and $x_{n+1}=\displaystyle\frac{4+x_n}{1+x_n}$ for $n\ge 1$. Prove by induction that for $n\ge 1$, ...
1
vote
2answers
350 views

Finding a non-recursive formula for a recursively defined sequence

So I have a recursive definition for a sequence, which goes as follows: $$s_0 = 1$$ $$s_1 = 2$$ $$s_n = 2s_{n-1} - s_{n-2} + 1$$ and I have to prove the following proposition: The $n$th term of the ...
3
votes
2answers
130 views

Prove that if $a_{n+1} = a_n^2$, the last $n$ digits of $a_{n+1}$ are the same as the last $n$ digits of $a_n$.

I have been working on this problem for a while. I know that I have to prove it using induction, but I'm unsure of the next step. The formula for the terms is: $a_{n+1} = 5^{2n}$ with $a_1 = 5$. The ...
-2
votes
1answer
418 views

A question on proving the sequence is bounded above by 2 [closed]

I'm still struggling to fully understand induction. Could someone help me find a way to prove, using induction, that the sequence $$x_1=1$$ $$x_{n+1}=\frac{1}{2x_n} + 1$$ is bounded above by 2; that ...
4
votes
5answers
919 views

Proving sum of $1/n^2$ is less than or equal to $2$ [duplicate]

So I'm suppose to prove that $\sum 1/n^2 \le 2$. Should I use induction?
6
votes
2answers
276 views

Prove that the sequence given by $c_n = \sqrt{1+c_{n-1}}$ converges and find the limit

Let $c_1 = 2$, and for $n > 1$, let $c_n = \sqrt{1+c_{n-1}}$. Prove: (by induction) that $c_n < 2$, for $n > 1$. (by induction) that {$c_n$} is monotonically decreasing. that ...
1
vote
3answers
404 views

Showing Whether a Sequence is Bounded Above or Not

I am trying to solve the following problem about a sequence: Consider the sequence ${a_n}$ where $a_n = 1 + \frac{1}{1 \cdot 3} + \frac {1}{1 \cdot 3 \cdot 5} + \frac {1}{1 \cdot 3 \cdot 5 \cdot 7} + ...
5
votes
2answers
967 views

Proving the AM:GM inequality

I am doing past exam papers preparing for the finals and I came across this questions about three times: Prove that: $$\frac{a_{1}+a_{2}+\cdots+a_{n}}{n}\geq \sqrt[n]{a_{1}.a_{2}...a_{n}}$$ ...
3
votes
6answers
206 views

Prove: $\frac{1}{1^2} +\frac{1}{2^2} + \cdots + \frac{1}{n^2} + \cdots = \sum_{n=1}^\infty \frac{1}{n^2} < 2$ [duplicate]

While I don't doubt that this question is covered somewhere else I can't seem to find it, or anything close enough to which I can springboard. I however am trying to prove $$\frac{1}{1^2} ...
1
vote
3answers
399 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) = ...
4
votes
1answer
218 views

Sum of alternating sign squares of integers stuck with proof by induction

Note that $$ A(1):1=1\\A(2):1-4=-(1+2)\\A(3):1-4+9=1+2+3\\A(4):1-4+9-16=-(1+2+3+4) $$ Let us set up the $A(k)$: $$ A(k)=1-4+9-…+(-1)^{k+1}k^2=(-1)^{k+1}(1+2+…+k) $$ Setting up $A(k+1)$: $$ ...
3
votes
2answers
63 views

Soving Recurrence Relation

I have this relation $u_{n+1}=\frac{1}{3}u_{n} + 4$ and I need to express the general term $u_{n}$ in terms of $n$ and $u_{0}$. With partial sums I found this relation $u_{n}=\frac{1}{3^n}u_{0} + ...
6
votes
10answers
1k views

Prove by mathematical induction that $1 + 1/4 +\ldots + 1/4^n \to 4/3$

Please help. I haven't found any text on how to prove by induction this sort of problem: $$ \lim_{n\to +\infty}1 + \frac{1}{4} + \frac{1}{4^2} + \cdots+ \frac{1}{4^n} = \frac{4}{3} $$ I can't ...