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

learn more… | top users | synonyms (2)

1
vote
1answer
51 views

Induction proof that if $C_1 = 0$ and $C_n = 4C_{\lfloor n/2 \rfloor} + n$ then $C_n \le 4(n-1)^2$

$C_1 = 0$, $C_n = 4C_{\lfloor n/2 \rfloor} + n$ Prove that $Cn$ less than or equal to $4(n - 1)^2$ What I did: Base step: n = 1 $C1$ <= $4(1 - 1)^2$ 0 <= 0 therefore true how do ...
3
votes
3answers
122 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
68 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 ...
2
votes
1answer
287 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
49 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 ...
2
votes
4answers
145 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
56 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
254 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. ...
1
vote
0answers
24 views

An expression for 2-dimensional element as a sum of differences of elements?

For 1-dimension, it's simple. $a_{n}=a_{1}+\sum_{i=2}^{n}(a_{i}-a_{i-1})$ But what would be the corresponding identity for 2-dimension? In other words, if we put $a_{n,m}=a_{1,1}+X$ then how can ...
2
votes
1answer
42 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
77 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
305 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
230 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
0answers
74 views

“Strange” plot of a difference equation

In this book about intertemporal optimization (page 33) I've found this difference equation: $x_{t+1}=ax_t \quad, \quad a>0$ The solution is: $x_t=a^t x_0$ where $x_0$ is the initial value of ...
1
vote
2answers
89 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
47 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, ...
3
votes
1answer
502 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
159 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
109 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 ...
2
votes
2answers
63 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
192 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
82 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
72 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
22 views

Difference $\Delta P_t$ approaches 0, then its relative difference $\Delta P_t / P_(t-1) \approx ln(P_t / P_(t-1))$.

When difference $\Delta P_t$ approaches 0, its relative difference $\dfrac{\Delta P_t}{P_{t-1}} \approx \ln(\dfrac{P_t}{P_{t-1}})$. I know that it can be shown somehow with Taylor series: ...
0
votes
1answer
75 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
29 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
277 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
45 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
210 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
129 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
53 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
44 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
478 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
131 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
54 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
4answers
4k 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 ...
0
votes
1answer
33 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
0
votes
1answer
55 views

Computation of $n$-th order difference of falling factorial

I was reading a difference equation textbook and came across a problem. The question asks to compute ${\Delta}^nt^{\underline3}$ for $n=1,2,3,...$, where $t^{\underline3}$ is the falling factorial ...
1
vote
1answer
185 views

Recurrence relation for Jacobi polynomials with negative parameter $\beta$

The Jacobi polynomials $P^{(\alpha,\beta)}_n(z)$ have the following recurrence relation in $n$ (see e.g. here): $2n(n+\alpha+\beta)(2n+\alpha+\beta-2)P^{(\alpha,\beta)}_n(z)$ ...
3
votes
3answers
260 views

Help me to solve this recurrence relation for a closed form

I've tried my best to solve this recurrence relation into a closed form formula for generality but I couldn't. So, is there someone to help me to solve this recurrence relation into a closed form ...
2
votes
1answer
72 views

Where can I find information on “Quadratic Maps”?

According to Wolfram, a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence relation: $$x_{n+1} = a ...
2
votes
0answers
42 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
0
votes
1answer
45 views

recurrence relation question.

I have this expression: $I_{n} = \int_0^1 \frac{x^{n-1}}{2-x} dx$ for $n=1,2,3,\ldots$ I have been asked to show that by writing $x^n = x^{n-1} (2-(2-x))$ that the recurrence relation $I_{n+1} = 2I_n ...
1
vote
2answers
126 views

Recurrence relation, generating function

I am trying to solve this recurrence relation using generating functions $$x_{n+2}+x_{n+1}+x_n=0$$ $$x_0 = x_1=1$$ I have got this generating function $f_a(x)=\frac{2x+1}{x^2+x+1}$. Since the ...
1
vote
1answer
45 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...
-1
votes
1answer
58 views

I am not how they got characteristic equation from the given equation.

![can someone tell me they got characteristic equation from the given recursive equation.][1] i know how to do the rest of problem but getting characteristic equation stopped me. The recurrence is ...
2
votes
1answer
122 views

Recurrence Relation.

I was searching the internet when I came a across a question, and just couldn't solve it. I kept rearranging and substituting but kept going around in loops. "For $n:= 1,2,3,.....,$ Let $$ I_n = ...
3
votes
1answer
139 views

Simple tax puzzle

I recently saw some post on facebook whining about taxes. Simplifying it (and changing numbers, facts, etc.), this was saying: For each dollar an employer wants to pay you: 20% go in taxes that ...
3
votes
1answer
158 views

General solution to Wright-Fisher model - Diploid selection

Wright-Fisher models are classical theoretical results in evolutionary biology. There are two discrete time models, one for haploid selection and one for diploid selection (the meaning of these models ...
0
votes
1answer
106 views

General solution to Wright-Fisher model - Haploid selection

Wright-Fisher models are classical theoretical results in evolutionary biology. There are two models, one for haploid selection and one for diploid selection (the meaning of these models does not ...