Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms

1
vote
3answers
58 views

What is $a_5$, given the recurrence $a_{n+1}=a_n+2a_{n-1}$ and we know that $a_0 = 4, a_2 =13$

I am having a very hard time figuring this out. So far I have been able to do the following: Writing the recurrence as a characteristic polynomial = $x^2-x-2=0$ so there are roots, $x=2, x=-1$. So ...
1
vote
1answer
397 views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: ...
1
vote
1answer
54 views

Recursive Sequence Proof

Take the function defined by $a_n= 3n + 1$, for all $n \in \mathbb{N} \geq 0$. Show that this sequence satisfies the recurrence relation $ a_k = a_{k-1} + 3$ $\forall k \in \mathbb{Z}, k \geq 1$. My ...
2
votes
2answers
204 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
1
vote
0answers
41 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
0
votes
1answer
81 views

Find a recurrent relation and generating function for the sequence

Let An be the nn matrix which has 1's on the leading diagonal and on the diagonals immediatle above and below the leading diagonal. Let an = det(An). Find a recurrent relation and generating ...
0
votes
2answers
34 views

Show Time $T(n) = Θ(n^3)$

I have to show that : $$T(n) = Θ({n^3})$$ We have this recursive function : $$T(n) = 8T(n/2) + n^2, n>=2$$ also we know that $$T(1) = 1$$ And it says that there is a "replacement method" to ...
2
votes
0answers
38 views

(limit of) a linear second order recurrence relation with variable coefficients

I have the following recurrence relation: $(n + 1) a_{n + 2} = (w (n + 1) - c) a_{n + 1} - z (n + 1)*a_{n}$ that I would like to either solve, or to get the $n$ goes to Infinity limit of the ratio ...
1
vote
1answer
74 views

Generating Function via Recurrence Relation

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated ...
2
votes
1answer
103 views

If $ x_{1} := 1 $ and $ x_{n + 1} := x_{n} + \dfrac{n}{(x_{1} \times \cdots \times x_{n})^{1/n}} $, then $ \dfrac{x_{n}}{\ln(n)} \to \infty $.

Define a sequence $ (x_{n})_{n \in \mathbb{N}} $ of positive real numbers by $$ x_{1} := 1 \quad \text{and} \quad \forall n \in \mathbb{N}: \quad x_{n + 1} := x_{n} + \frac{n}{(x_{1} \times \cdots ...
7
votes
4answers
256 views

How can I solve this linear recurrence relation?

My problem is: this given recurrence relation: $$y_{n+1}-\frac{n+2}{2}\cdot y_n = (n+1)(n+2)\cdot 3^n$$ for all: $n\ge 0$ and $y_0 = 0$ I need to find the explicit form and the general solution. My ...
-1
votes
1answer
38 views

Solving recursion formula with sum [closed]

i am trying to solve the following recurrence, but i am stuck... $$t(n)=n + \sum_{j=1}^n t(n-j)$$ I really appreciate your help,
0
votes
1answer
105 views

Differential Equations: Find the first four terms in each of two solutions y1 and y2 …

The differential equation is $y'' - xy' - y = 0$ with $x_0 = 1$ Now, I know how to find the recurrence relation... and it's given by: $a_(n+2) = [(a_(n+1) + a_(n)) / (n+2)]$ But I can't quite ...
0
votes
1answer
42 views

$a_1=3$ and $a_{n+1}=\dfrac{2a_n}{3}+\dfrac{4}{3a_n^2}$. Show that $4^{1/3} \le a_n$for all $1\le n$.

$a_1=3$ and $a_{n+1}=\dfrac{2a_n}{3}+\dfrac{4}{3a_n^2}$ By considering the function $f(x)=\dfrac{2x}{3}+\dfrac{4}{3x^2}$, show that $4^{1/3} \le a_n$ for all $1\le n$.
1
vote
1answer
42 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
2
votes
0answers
129 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
1
vote
0answers
237 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
3
votes
3answers
97 views

Recurrence relation question. Homework.

A certain counting sequence $T(n)$ has generating function $$\frac{x}{1-3x}=\sum_{n=0}^{\infty}T(n)x^n.$$ (a) Derive a simple recurrence relation for $T(n)$. (b) Give a simple explicit formula for ...
1
vote
2answers
63 views

How to solve this mathematically

This is a question given in my computer science class. We are given a global variable $5$. Then we are to use keyboard event handlers to do the following: On event keydown double the variable and on ...
1
vote
1answer
143 views

Finding recurrence relation given the generating function

So I'm given the generating function $F(x)={1+2x\over1-3x^2}$ I'm supposed to find the recurrence relation satisfied by fn. I managed to get it into 2 separate geometric series and derive $f_n = ...
1
vote
0answers
35 views

Help Solving a Recurrence Relation with an Inverse Term

I am having a hard time generating a characteristic polynomial for a recurrence relation I thought of the other day, $a_n = a_{n-1} + \frac1{a_{n-1}}$. I am pretty familiar solving basic recurrence ...
0
votes
1answer
64 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
0
votes
1answer
44 views

Exponential Generating Function - Bona (3rd Edition) Ch. 8 #29

Let $a_0 = 0$, and let $a_{n+1} = (n-1)a_n + n!$ for $n \ge 0$. Find an explicit formula for $a_n$. I have gotten to the point where I have $\sum_{n \ge 0}a_{n+1}\frac{x^{n+1}}{(n+1)!}=\sum_{n \ge ...
1
vote
0answers
113 views

Help with find recurrence relation running time.

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. ...
2
votes
1answer
33 views

Simple recurrence relation - 1D

I know this is a very simple recurrence relation, but how would you go on solving it? $$x(n+1)=\frac{x(n)}{1+x(n)}$$
1
vote
1answer
67 views

Sequence Convergence and Limits

Here is a problem I've been working on. I am stuck and wondered if you guys could shed any light. Let $a>0$ and $u_{1}>a$. Consider the sequence $(u_{n})_{n=1}^{\infty }$ defined by: $$ ...
1
vote
2answers
159 views

Counting problem using exponential generating functions

From A Walk Through Combinatorics by Bona in the section on generating functions We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, ...
0
votes
3answers
183 views

Recurrence relations problem

Don't understand why someone would assign problems that he hasn't reviewed... It's crazy... I ask for help and got that response lol If $S_{n+2} = 2S_{n+1} - S_n + 3$, what are the correct steps in ...
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
32 views

Writing a recurrence in terms of a shift operator

This is a concept that I vaguely understand, but I'd like to get an intuitive understanding of how to write a recurrence relation of the form: $$ t_{n}-3t_{n-1}+2t_{n-2}=0 $$ subject to $$ t_0=2, ...
1
vote
1answer
98 views

Concrete Mathematics - Stability of definitions in the repertoire method

There are some existing questions on the repertoire method from the first chapter but I think I'm stuck on something different than the part people usually have trouble with. I think the jump in the ...
3
votes
2answers
136 views

Google Question: Number of ways to select sets such that n is pure

Consider a subset $S$ of positive integers. A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
0
votes
1answer
65 views

Fractional-Recursive Sequence

Here from the fraction set we have a really hard question to be answered...suppose that a sequence is defined as a(n) = a(n-1) - 1/a(n-1), where a(0) is given. ...you already know what I'm asking you ...
0
votes
0answers
31 views

Recurrence relation over a finite field?

I am trying to solve a typical calculation problem about recurrence relations over a finite field. So, given is some polynomial $f(x)$ over $F_{11}$, about this polynomial we know that its highest ...
2
votes
2answers
50 views

Recurrence Relations and Characteristic Equations

I am not understanding how to go from the beginning of a recurrence relation to the end. I do not understand how to get to the characteristic equation. I can factor it if I know where it comes from. ...
0
votes
1answer
65 views

Recurrence Relation for Optimal Card Game Score

I have the following problem where Alice and Bob decide to play a simple card game. At the beginning of the game, $n$ cards are dealt face up in a long row. Each card is worth a different number of ...
2
votes
1answer
56 views

Recurrence relation of an integral [closed]

$$ y_n = \int_0^1 \frac{x^n}{x+5} dx,\ \ n=0,1,2,...,\infty $$ What is the recurrence relation between $y_n, y_{n-1}$ ? Could you provide me a methodology on how to proceed with this?
1
vote
3answers
69 views

Still a novice could use a little help

Ok, so I have this question, and we never went over this or how to solve it in class. I can't find an example in the book either. How do I show that $f_n = 3^nA + 2^nB$ satisfies the recurrence ...
0
votes
1answer
71 views

Solving this recursive function $f(x)=f(x-k)+f(x/k)$.

How to solve or simplify the following recursive function? $f(x)$ is defined only for whole numbers as follows: $$f(x)=\begin{cases} 1 & \mbox{if } x<k; \\ f(x-k)+f(x/k) ...
0
votes
1answer
26 views

Linear homogeneous recursive sequence of constant sign

Let recursive sequence be defined by the formula $$ s_{j+1}=as_j-s_{j-1}, $$ where $a>1$ is some integer number. Is it true that $s_0<0$, $s_1<0$ implies $s_j<0$ for $j \geq 0$? Edit: ...
1
vote
1answer
108 views

recurrence relations for computation the number of n-digit binary sequences

Find a system of recurrence relations for computation the number of n-digit binary sequences with an even number of 0 and an even number of 1.
1
vote
3answers
40 views

Average value of recurrent function.

Given a function f(x) = a*f(x-1) where a is a number between 0 and 1, what is the average value of ...
0
votes
1answer
56 views

Recurrence Relation Models

Find a recurrence relation for $a_n$, the number of ways to give away $1$, $2$, or $3$ for $n$ days with the constraint that there is an even number of days when $1$ is given away.
-1
votes
1answer
86 views

Is $2^n \mod m \equiv (2^{n/2} \pmod m ) ^ 2 \pmod m$?

I'm trying to write a procedure that solves (2^n - 1) mod 1000000007 for a given n. n can ...
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
1answer
35 views

Characteristic roots-recursion.

I have very simple question about characteristic roots of recursion problems. Lets say we have characteristic equation: $r^2 - 5r + 6 = 0$. It has roots $r=2$, $r=3$. When plugging this into $a_n = ...
2
votes
1answer
165 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
1
vote
1answer
67 views

Matrix powers and recurrence relations

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? ...
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 ...
1
vote
4answers
855 views

how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms? what i know is The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum ...