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

learn more… | top users | synonyms (2)

1
vote
0answers
17 views

Convergence of a recurrence relation

Some background information. I'm trying to estimate four probabilities $(p_1, p_2, p_3, p_4)$ (sum is equal to one) from nine numbers $(n_1, \dots, n_9)$ using Maximum Likelihood. (All $n_i$'s are ...
1
vote
2answers
35 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
1
vote
0answers
44 views

Coefficients of the polynomials generated by $f_0=x,\ f_{i+1}=f_i\pm\dfrac1{f_i}$.

Let $f_0=x,\ f_{i+1}=f_i\pm\dfrac1{f_i}$ for $i\geq0$, i.e., $f_i=\dfrac{\sqrt{f_{i+1}^2\mp4}+f_{i+1}}2$ I have observed that $f_1=\dfrac{x^2\pm1}x$ $f_2=\dfrac{x^4\pm3x^2+1}{x(x^2\pm1)}$ ...
1
vote
1answer
115 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
1
vote
1answer
53 views

Recurrence equation solution?

Can you help me with the solution of this recurrence equation? $$ f(n+2) = -2f(n) +3f(n+1) +n \quad\mid\quad f(1)=4 \quad\mid\quad f(2)=5 $$ Thank you.
1
vote
1answer
54 views

What Did I Do Wrong When Solving For This 2nd Order Differential Equation? (answered myself)

$$ \frac{y''}{y'}+y' = f(x) $$ I set the following to be true: $$ y = \sum_{n=0}^{\infty} a_n x^n $$ $$ f(x) = \sum_{n=0}^{\infty} b_nx^n $$ Therefore: $$ y'' = y'(f(x)-y') $$ $$ ...
1
vote
1answer
109 views

recurrence relation with variable coefficients

How to solve recurrence relation $y(n)= y(n-1)+ (n-1)y(n-2)$ where $n$ is a variable ? $y(n)$ is a $n$th term, $y(n-1)$ is $(n-1)$th term and $y(n-2)$ is $(n-2)$th term.
1
vote
1answer
82 views

Legendre Series Recurrence Relation Divergence at $x=\pm1$, using Gauss test

How to show that the Legendre Series solution $y_{even}$ and $y_{odd}$, diverges as $x = \pm1 $. $y_{even} = \sum_{j=0,2,\ldots}^\infty a_jx^j$, where $a_{j+2}=\frac{j(j+1)-n(n+1)}{(j+1)(j+2)}a_j$. ...
1
vote
1answer
62 views

How to solve this multivariable recursion?

How to solve this multivariate recursion?: $$a(m, n, k) = 2a(m-1, n-1, k-1) + a(m-1, n-1, k) + a(m-1, n, k-1) + a(m, n-1, k-1)$$ where $m, n, k$ are positive integers. Edit: $a(0,0,0) = a(1,0,0) = ...
1
vote
0answers
36 views

Interesting recurrence equation models?

So I've had an introductory subject to recurrence equations and now I have to study a model using recurrence equations as a project. The problem is that most models I find are either elemental or ...
1
vote
1answer
99 views

How to solve a recurrence relation such as $T(n) = 2T(\frac{n}{2}) +$ $\frac{n}{\log (n)}$?

Wikipedia says that the equation cannot be solved using Master's Method. The equation matches with Master's Theorem except for $\frac {n}{\log(n)}$. A youTube tutor (seek time 11:42) solves this ...
1
vote
1answer
17 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
1
vote
0answers
25 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
1
vote
1answer
83 views

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined? [duplicate]

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself. ...
1
vote
0answers
42 views

2nd order difference equation with n dependent coeff

I wanted to know if there was and solution to the following equation. $\left(N-n+1\right)E_{n+2} - NE_{n+1} + \left(n+1\right)E_{n} + N = 0$ Where $E_0 = 0$ and $E_1 = 2^N - 1$. $N$ is just a ...
1
vote
0answers
86 views

$T(n) = T(n/2 - \log(n)) +1$ using Substitution Method

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method? I don't fully understand the theory of this method and I'm not sure how to apply ...
1
vote
0answers
61 views

Solution of $x_{k+1} = x_{k} (a x_{k} + b)$

Could anyone help me to solve the equation $x_{k+1} = x_{k} (a x_{k} + b)$, for find the explicit solution of $x_{k}$? BTW. Do you know a GOOD book for the classification for non linear difference ...
1
vote
2answers
44 views

Solve the linear homogeneous recurrence relation with constant coefficients

$$9a_{n} = 6a_{n-1}-a_{n-2}, a_{0}=6, a_{1}=5$$ So $$x^n = (6x^{n-1}-x^{n-2})\div9$$ thus $$[x^2 = (6x-1)\div9] \equiv [x^2 - \frac{2}{3}x + \frac{1}{9} = 0], x=\frac{1}{3}$$ also ...
1
vote
1answer
28 views

Solve linear homogeneous recurrence relation?

The relation to solve is this: $$ a_{n} = 7a_{n-1} - 10a_{n-2}, a_{0} = 5, a_{1} = 16$$ So $$ a_{2} = 62, a_{3} = 274, ...$$ So I thought I was supposed to be able to do this to solve: $$ x^n = ...
1
vote
0answers
21 views

binomial coefficient and recurrence relation [duplicate]

any hints on how to solve the recurrence relations for the following binomial coefficient \begin{equation} {n \choose k}=\begin{cases} 1, & \text{if $k\in\{0,n\}$}.\\ {n-1 \choose ...
1
vote
1answer
44 views

Difference equation with log

Can we find continuous $f(x)$ and $d$ such that $$ f(x+1)-f(x) = -\log( c|x| + d ) $$ for all $x$? The constant $c>0$ is specified.
1
vote
0answers
27 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
1answer
32 views

Help to describing a recurrence for $l_n$

I have to describe a recurrence for $l_n$, the number of lobsters caught in year $n$. The task says: a hobby fisherman estimates the number of lobsters he will catch in a year as the average of the ...
1
vote
0answers
89 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
1
vote
0answers
30 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
1
vote
2answers
86 views

Solving recurrence relation $f(n) = f(\lfloor\sqrt n\rfloor) + 1; f(1) = 1, f(2) = 1$

As the title shows, I need help approaching a solution for recurrence relation: $f(n) = f(\lfloor\sqrt n\rfloor) + 1$ if $n\ge3$ with initial values $f(1) = 1$, $f(2) = 1$ I am particularly ...
1
vote
0answers
39 views

Recurrence relation sequence (Hard)

I was wondering if this sequence was possible using two base cases? The sequence is $\{-1,0,1,3,13\}$ .. Ive came close by doing $(a_{n-1})^2+a_{n-2}+a_n-1$ which works for everything but the $1$. I'm ...
1
vote
2answers
55 views

Question about recurrence relation problem.

solve the following recurrence relation, subject to given initial conditions. $a_{n+1} = 6a_n -9,$ $a_0 = 0,$ $a_1 = 3.$ Here is what I have done. $a_{n+1} - 6a_n +9 = 0$ $a_n = r^n$ $r^{n+1} ...
1
vote
0answers
45 views

Difference equation of second order system with zero

I saw from lecture notes that difference equation of a first order system is like this: (1) (2) (3) (4) 1. What happens between (3) and (4)? It looks like inverse Z-transform but according ...
1
vote
0answers
15 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
1answer
29 views

Linear recurrence by characteristic equation.

Consider the linear recurrence $a_n = 2a_{n−1} − a_{n−2}$ with initial conditions $a_1 = 3, a_0 = 0$. We have $x^2 − 2x + 1 = (x − 1)^2$. Thus $ x = 1$ and $a_n$ = $u(1)^n + v(1)^n$. Why do we get ...
1
vote
1answer
45 views

How do I solve for the recurrence relation when P does not exist?

I'm using the method that my textbook uses. I first put the recurrence relation in the form of a matrix. After that I solve for the eigenvalues and eigenspaces to find P. Then they use P to find D and ...
1
vote
0answers
42 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
1
vote
0answers
32 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
1
vote
0answers
31 views

How to solve these recurrences

I have this recurrence and I have tried to solve it but I am completely lost. Master Theorem cannot be applied on this at-least not without some substitution or stuff. $ i)\quad T(n) = 4 T( \left ...
1
vote
1answer
14 views

Using a recursion tree to obtain an algorithm classification with n^2 time

I'm having trouble getting the classification of this recurrence relation using a recursion tree. $$T(n) = 3T(n/2) + n^2$$ I have the tree written out correctly (I hope): ...
1
vote
0answers
73 views

What is the recurrence relation between $a_n, a_{n-1}$ , $a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx$

I would appreciate if somebody could help me with the following problem Q: What is the recurrence relation between $a_n, a_{n-1}$ ? $$ a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx,\ \ ...
1
vote
1answer
30 views

Getting recursive formula to since solution

Is there any way to get the recursive formula of the form $r_n=\alpha r_{n-1}+\beta$ to single formula as a function of $n$. I've seen results that find single formula as function of $n$ for geometric ...
1
vote
0answers
65 views

Non-recursive closed-form of the coefficients of Taylor series of the reciprocal gamma function

The reciprocal gamma function has the following Taylor series. $$\frac{1}{\Gamma(z)}=\sum_{k=1}^{\infty}a_kz^k,$$ where the $a_k$ coefficient are given by the followint recursion. $a_1=1$, ...
1
vote
0answers
33 views

Complicated 2-variable recurrence

I am analyzing some kind of construction for which size satisfies the following recursion: $P(n,k)=\frac{k}{2}\log \frac{k}{2} + 1 + \frac{n}{2} + P(\frac{n}{2},k) + P(\frac{n}{2},\frac{k}{2})$ ...
1
vote
1answer
65 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? ...
1
vote
0answers
48 views

Recurrences with modulo

Is there any specific way to solve recurrence of form (example): $$f(x) = (a \cdot f(x-1) + c) \bmod{r} $$ (when recurrence involves modulo). For recurrence without modular arithmetic I could use ...
1
vote
1answer
64 views

Solving a recurrence using the Master Theorem where $f(n) = log(\log n)$

I have the recurrence $$T(n) = 3\,T(n/2) + \log(\log n)$$ I take $a = 3$, $b = 2$ and $f(n) = \log(\log n)$. I also have $\log_2 3 = 1.585$. I'm not sure how to approach a log inside of a log. Would ...
1
vote
0answers
35 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
1
vote
1answer
53 views

Expanding a recurrence relation with a summation involved

Question: $(10)$ Solve the recurrence in asymptotically tight big Oh function; $$t(n)=n+\sum_{i=1}^kt(a_in),$$ for the two cases (a) where $\sum_{i=1}^k a_i < 1$, and (b) where ...
1
vote
2answers
26 views

Solving a recurrence equation that yields polynomials

I am trying to solve the following recurrence equation: $$ T(n) = kT(n - 1) + nd $$ I have expanded the first 4 values ($n = 1$ was given): $$\begin{align} T(1) & = 1 \\ T(2) & = kT(2-1) + ...
1
vote
1answer
97 views

Recursive Solution to Interest with Monthly Deposits

I open an account at a bank with 1% interest compounded monthly. I'm adding $100 to it at the beginning of each month (starting with month 1). (a) Set up a recurrence relation for the amount in the ...
1
vote
1answer
38 views

use substitution method to prove an equation is in O(n log2 n)

I am trying to prove that the equation: T(n) = 2T((n/2) +17) + n is O(n log_2(n)) I have to do this by using substitution ...
1
vote
2answers
60 views

How do you solve these recurrence relations for a closed form?

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of ...
1
vote
1answer
26 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...