2
votes
3answers
41 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
0
votes
1answer
34 views

Could someone explain me this induction.

I'm trying to understand a paper called "Diameter of Polyhedra: Limits of Abstraction" available here : http://sma.epfl.ch/~eisenbra/Publications/designs.pdf My problem is with the first two ...
0
votes
2answers
46 views

Use Bonnet recursion formula to prove by induction

Use Bonnet recursion formula: $P_{n+1}(x) = \frac{2n+1}{n+1} x P_n(x) - \frac{n}{n+1} P_{n-1}(x)$ to prove by induction 1) $P_n(1) = 1$ for all $n$ 2) $P_n(-x) = (-1)^n P_n(x)$ for all $n$ an for ...
0
votes
1answer
26 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
45 views

Cayley's formula for the number of trees(Recursion)

I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all. -It ...
-1
votes
0answers
41 views

What is wrong with this induction proof for a closed form recursive function?

I need some help, I can't seem to find What is wrong in this proof, yet I'm not getting what I need. Anyone know? Prove by induction $2(S(2^{k-1})) + 2^k = 2(2^{k-1})k +2^k$, given that: $S(2^0 ) = ...
0
votes
0answers
23 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
2
votes
2answers
41 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$ ...
0
votes
1answer
35 views

Using induction to prove a general form from a recurrence relation

I have the recurrence relation: $a_{n+2} = \dfrac{-a_{n}}{(n+2)(n+1)}$. I have done some work to identify that two cases emerge: one is n is positive, and one if n is negative. If n = 2m (even) ...
3
votes
1answer
99 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
1
vote
1answer
70 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
27 views

Proving the monotonicity of a recurrence.

Define the following recurrence for $n = 1, 2, \cdots$ $T(n) = ( 1 - \operatorname{H}(\frac{1 - P^{\frac{1}{n}}}{2}))^n$ where $0 < P < 1$ is a constant, function $\operatorname{H}(\cdot)$ is ...
1
vote
1answer
46 views

Finding the explicit formula for the succession $x_0=2, x_{n+1} = 5x_n$ and proving it with induction

I'm trying to learn about recursion, first with this exercise: Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$ So, from what I've seen, I should test a bit. I see that the ...
1
vote
1answer
164 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
2
votes
4answers
104 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 ...
1
vote
2answers
77 views

Induction Proof (relating two recurrences)

Let $L(n) = n + 2 L\left(\frac{n}{2}\right), \, L(1) = 1,$ and $U(n) = 9n + 2U\left(\frac{n}{2}\right), \, U(1) = 9.$ Prove by induction that $U(n) = 9L(n)$ where $n = 2^k$. I attempted to prove ...
0
votes
1answer
45 views

Solve non-linear recurrence

I am trying to solve the following recurrence (i.e. determine $a_n$). I'm not entirely sure how to proceed, I have only encountered linear ones so far. This is not a homework, I'm just doing it for ...
0
votes
2answers
40 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 ...
2
votes
3answers
68 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$
0
votes
3answers
177 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
0
votes
1answer
61 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
1answer
65 views

Is this recursion well-defined?

I have a recursion defined by $$ f(n)=\max\{0,-c+pf(n-1)+(1-p)f(n+1)\} $$ with $0.5<p \leq 1$ and $f(0)=R>0$ and $f(m)=0$ for some $m>0$. I am trying to show that $f(n)$ is decreasing in ...
-2
votes
2answers
52 views

what is the inductive polynomial coefficients

Let $\{f_n(x)\}_{n\in \Bbb N}$ be a sequence of polynomials defined inductively as $$\begin{matrix} f_1(x) & = & (x-2)^2 & \\ f_{n+1}(x)& = & (f_n(x)-2)^2, &\text{ for all ...
0
votes
1answer
199 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
1
vote
3answers
124 views

Using complete induction, prove that if $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$, then $a_n=2^n$

Could anyone please explain to me how to do this problem by using the principle of complete induction? Thanks. :) Let $a_1=2$, $a_2=4$, and $a_{n+2}=5a_{n+1}-6a_n$ for all $n\geq 1$. Prove that ...
1
vote
1answer
54 views

Prove by induction that $d_n=2^n+3^n$, where $d_n = 5d_{n-1}-6d_{n-2}$

I have one more induction question. $d_0 =2 $ $d_1=5$ let $d_n=5d_{n-1} - 6d_{n-2}$ Prove that $d_n=2^n+3^n$
0
votes
2answers
31 views

recurrence relation with induction

The following recurrence relation: $T(n)=T(n-1)+n=1+\frac{n^2+n}{2}=\theta(n^2)$, so this mean that: there is $c_1, c_2, n_o > 0 : c_1n^2<=1+\frac{n^2+n}{2}<=c_2n^2$, the second inequality ...
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} + ...
1
vote
1answer
127 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
0
votes
1answer
258 views

Solving Recurrence Relation with Forward Substitution

I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with $$ T(n) = 4T(n/3) $$ For all $n > 1$ ...
0
votes
1answer
146 views

Induction hypothesis when proving solution to linear homogeneous recurrence equation

I am looking at an example solution to a linear homogeneous recurrence equation of: $T(0) = 0$ $T(1) = 2$ $T(n) = 4T(n-1) - 3T(n-2), n > 1$ And solving it you get $T(n) = 3^n - 1$ In the ...
0
votes
3answers
67 views

Recursive/Fibonacci Induction [duplicate]

1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction: $$ F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}} $$ Clear ...
1
vote
2answers
170 views

Difference between two methods of induction for proving the correctness of recurrence equation solution

Suppose you have the recurrence equation $T(0) = 0$ $T(n) = 2T(n-1) + 1, n > 0$ The closed form of this equation appears to be $T(n) = 2^n - 1$ To prove this is correct using induction, we have ...
0
votes
4answers
293 views

Having a lot of trouble solving this recurrence with iteration and finding a closed form…

I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, ...
0
votes
0answers
61 views

proving an inequality by induction

Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious. $t_{r+1} \leq (r+1) (t_r ...
1
vote
1answer
76 views

Prove by Induction $\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}} = \left[\frac{a_1-\sqrt{A}}{a_1+\sqrt{A}}\right]^{2^{n-1}} $

$a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$; $a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$; and $a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n \geq 2$; where $a\gt 0$, $A\gt 0$. Prove: ...
2
votes
1answer
451 views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + ...
0
votes
1answer
41 views

How can I prove a sequence of values follows a certain closed form equation?

For example, imagine I'm trying to do this $$ (1-3x+3x^2)/(1-3x+3x^2-3x^6) = \sum\limits_{n=0}(a_nx^n) $$ $$ (1-3x+3x^2) = \sum(a_nx^n) * (1-3x+3x^2-3x^6) $$ Then say we are given some closed ...
12
votes
5answers
364 views

Alternate proof that for every natural number $n,\ \left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$ is divisible by $3$

Original Problem: Prove that for every natural number $n$,$$\left\lfloor\left(\frac{7+\sqrt{37}}{2}\right)^n\right\rfloor$$ is divisible by $3$. I found the problem in the book Winning ...
2
votes
3answers
136 views

Mathematical induction proof; $g_k=3g_{k-1} - 2g_{k-2}$

Can someone help me with this problem? I'm having a hard time proving this. It's been a long time since I have done mathematical proofs. Suppose that $g_1,\ g_2,\ g_3,\ \ldots$ is a sequence of ...
0
votes
1answer
123 views

Proving the equality of 2 functions

You are given that $f(n)=g(n, f(n-1))$ (some initial values given). Looking at the first few terms, it becomes obvious that $f(n)=h(n)$. How does one go about proving this? Induction seemed obvious ...
0
votes
0answers
350 views

Proving a recurrence relation by induction

Hi I have the following recurrence relation: $$T(n) = \begin{cases} 1, & \text{if $n=2$} \\ 2T\left({n \over 2}\right) + 4, & \text{if $n > 2$} \\ \end{cases}$$ Where $n$ can be ...
2
votes
1answer
63 views

Flawed twofold induction on an inequation (but where?)

The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...
0
votes
1answer
97 views

Demonstration of a recurence formula

I would like to demonstrate a recursive formula that I have inferred. My background in mathematics is not quite as high as I hoped and although I have tried to apply the basic tricks that go with the ...
2
votes
2answers
940 views

Recurrence $T(n)=2T([n/2]+17)+n$ and induction.

Show that the solution to $$T(n) = 2T\left(\biggl\lfloor \frac n 2 \biggr\rfloor+17\right)+n$$ is $\Theta(n \log n)$? So the induction hypothesis is $$ T \left( \frac n 2 \right) = c\cdot \frac n2 ...
1
vote
2answers
834 views

prove a monotonically increasing function from recurrence relation by induction

How to prove $T(n)$ is a monotonically increasing function by induction provided that $T(n) = T(n/2 + \sqrt{n}) + \sqrt{6046}$? $n$ is larger than $n/2 + \sqrt{n}$ when $ n \geq 5$ and it is ...
1
vote
1answer
58 views

Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction for the sequence $x_{n+1}=x_{n} + (n+1)^3$

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions. I'm a bit lost as to how to start the induction ...
4
votes
3answers
197 views

If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$

I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question. Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$. ...