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

learn more… | top users | synonyms (2)

1
vote
0answers
24 views

Deriving binomial distribution from a recurrence.

Let $X_n, n\geqslant1$ be iid random variables with distribution $\mathbb P(X_1=1)=p = 1 - \mathbb P(X_1=0)$. Let $S_0=0$ and $S_n=\sum_{i=1}^n X_i$, $n\geqslant1$. Let $q_{n,k}=\mathbb P(S_n=k)$, for ...
0
votes
1answer
23 views

Computation Operation in one Recurrence Relation

We want to calculate $T(n)$ from recurrence relation $ T(n)= \Sigma_{i=1}^{n-1} T(i) \times T(i-1)$` and we know $T(0)=T(1)=2$. How many computation operation, an Efficient Algorithm needs for ...
2
votes
0answers
67 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
1
vote
0answers
33 views

Sequence from generating function.

Consider the recurrence $$\mu_1=1, \mu_2=2, \mu_3=4, \mu_4=8, \mu_5=16, \mu_6=32 $$ and $$\mu_{n+6} = \mu_n + \mu_{n+1} + \mu_{n+2} + \mu_{n+3} + \mu_{n+4} + \mu_{n+5}, n\geqslant 1. $$ The generating ...
0
votes
3answers
41 views

Generating Function for a Recurrence Relation $a_n=a_{n-1} + n$

Find a generating function for $\{a_n\}$ where $a_0=1$ and $a_n=a_{n-1} + n$
0
votes
0answers
32 views

Sum of harmonic series depending on n

I am trying find a solution to a recurrence by using recursion tree and substitution method. My recurrence is $T(n) = T(n-1) + 1/n; T(1) = 1$. After drawing the tree I get the following sum: $1/(n-i)$ ...
1
vote
1answer
44 views

Solving a difference equation with several parameters

Let $r>4$ be a positive integer. Let us consider this difference equation: $$u_{q+1}=(r^{2q+1}+(c/a))u_{q}-(c/a)r^{2q-1}u_{q-1} +2c+d-(bc/a)$$ where $a,b,c,d$ are integers. I want to find a ...
4
votes
1answer
57 views

A reccurent sequence

Let $(a_n)$ a sequence such that: $a_1=1$ and $a_2=2$ and $a_3=3$ such that $a_n=\frac{a_{n-1}a_{n-2}+7}{a_{n-3}}$ show that $ a_n \in \mathbb{N} $ I tried to find a particular form of the ...
0
votes
0answers
40 views

recursive-algorithm problem

I am not to sure were to begin Thanks
1
vote
1answer
54 views

Closed expression for $y^{(n)}$ when $y' = ay$

I'm interested in tidying up the calculation of arbitrarily high order derivatives of a function containing an exponential. Although any function can have it's derivative expressed as ...
0
votes
0answers
95 views

Recurrence relation $F(n) = 2F(\sqrt n) + 1$

I'm stuck with the following recurrence relation: $F(n) = 2F(\sqrt n) + 1, n \in \mathbb{N}$ I considered $n = 2^{2^{k}}$ and then expanded the recursion and here is what I get $F(n) = F(2^{2^{k}}) = ...
0
votes
1answer
23 views

Recursion Tree: leaves at bottom level equals n^(log b / log a)?

My book says that the total number of leaves on the bottom level equals n^(log a / log b), with T(n) = a * T(n / b) + f(n). How do they come up with this? Say I have a function 3 * T(n / 4) + f(n) ...
1
vote
0answers
25 views

Did i multiply the sums correctly?

This is an extention to this question except i am unsure of whether i have done it correctly: $$ y'' = -y'(f(x) - r(x) y') $$ $f(x) = \sum_{n=0}^\infty s_n x^n$, $y = \sum_{n=0}^\infty a_n x^n$, and ...
0
votes
1answer
52 views

Use recursion tree to give an asymptotically tight solution of T(n)

Assume $T(1) = 3.$ Recurrence is $T(n)=T(n-3)+3n+1$ and I'm showing $\Theta$ bound by computing the exact running time. Starting off: $(Tn-3) + 3n + 1$ $(Tn-9) + 9(n-3) + 3n + 1$ $(Tn-18) + ...
0
votes
1answer
54 views

Tight bound for $T(n) = T(n^{1/2}) + 1$ [duplicate]

Can someone help me figure out the big-O for the recurrence relation $T(n) = T(n^{1/2}) + 1$? I didn't think the master theorem would work since it requires $T(n) = T(n/b)$... to have $b$ as a ...
0
votes
1answer
67 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...
1
vote
0answers
36 views

solve third order scalar using 3 by 3 matrix recursion

Suppose I have something like the following: $$t(n+2) = 3t(n+1) - 2t(n) + t(n-1)$$ I do not want a complete solution to this question. All that I would like to know is how to convert this into a 3 ...
0
votes
0answers
13 views

Finding a pattern and solving a recurrence using repeated substitution

I am trying to understand how to solve the following recurrence using repeated substitution: $lgn = \log_2n$ $$T(n) = 3T(n/3) + n/lgn$$ I then substitute a few times to try and discern a pattern: ...
0
votes
2answers
86 views

Recurrence Relations With Exponents

Solve the following: $$a_n = 2a_{n-1} + 2^{n-1} , a_0 = 3$$ Workings: $a_n = 2a_{n-1} + \frac{1}{2} 2^n, a_o = 3$ $a_n^{(h)} = 2a_{n-1}$ The characteristic equation is: $ch(x) = (x-2)$ ...
4
votes
2answers
87 views

Of fibonomials, pellonomials, and tribonomials, etc

I. Linear recurrence with order 2 Given the Fibonacci numbers $F_n$, we have $$\begin{aligned} &F_n+F_{n+1}-F_{n+2}=0\\[1mm] &F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm] ...
0
votes
0answers
38 views

Need help with recurrence problem that asks for asymptotic upper and lower bounds

Problem sounds like that: Give asymptotic upper and lower bounds for $T(n)$. Assume that $T(n)$ is constant for $n<=2$. Make your bounds as tight as possible, and justify your answers. $$T(n) = ...
3
votes
0answers
35 views

Algorithms - Solving the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ [duplicate]

I have been trying to solve the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ for some time now. I only know substitution, recursion trees, and the master method (though it doesn't apply ...
2
votes
0answers
57 views

Generalizing the Fibonacci identity $F_{2n}=-F_{n-1}^2+F_{n+1}^2$

Using an integer relations algorithm, we get, $$F_{2n}=-F_{n-1}^2+F_{n+1}^2$$ $$6F_{4n}= -F_{n-2}^4-3F_{n-1}^4+3F_{n+1}^4+F_{n+2}^4$$ The pattern of the subscripts is clear. Expressing the ...
1
vote
2answers
37 views

Recurrence relation!

I want to know how to compute $H(n) = H(n-5) + \frac{n}5$ I know how to solve the recurrence relations whose difference between LFS and RFS is 1 (ex. $H(n) = H(n-1) + n$) but I have no idea how to ...
0
votes
0answers
23 views

How to solve this biparametral recurrence relation?

I have a problem that reduces to solving the following recurrence relation: $$X(2, 1) = 1, \ \ \ X(n, 0) = 0, \ \ \ X(n, k \geq n) = 0$$ $$X(n, 0 < k < n) = \frac{k-1}{n-1} X(n-1, k-1) + ...
1
vote
0answers
23 views

Did i generalize this series solution correctly?

$$ f(x) = \frac{y''}{p(x)y'} + r(x) y' $$ if all functions are expressed in their power series form, then: $$ y = \sum_{n=0}^\infty a_nx^n $$ $$ p(x) = \sum_{n=0}^\infty p_n x^n $$ $$ r(x) = ...
0
votes
2answers
23 views

Guidance on solving a recurrence relation

I am trying to solve the following recurrence: $T(1) = 2$, and for all $n\ge2$, $T(n) = T(n-1) + n - 1$ By using repeated substitutions, I was able to discern the following formula: $$T(n)=T(n-i) + ...
1
vote
1answer
29 views

Show $x_{r+1}$ defined as $x_{r}/2$ for $x_r$ even and $3x_{r}+1$ for $x_r$ odd goes to $1$ for all positive integer $x_0$. [duplicate]

Consider the following recurrence relation: $$x_{r+1} = \left\{\begin{matrix} x_{r}/2 &\text{if }x_r\text{ is even}\\3x_{r}+1&\text{if }x_r \text{ is odd}\end{matrix} \right. $$ I wrote ...
0
votes
0answers
18 views

How do I solve this linear homogeneous recurrence problem?

Note: My math background is really weak. Please explain like explaining to a 5th grader. Find the solution: $a_n=a_{n−1}+a_{n−2}$ with $a_0=0$ and $a_1=1$ (Fibonacci) This is similar to this: Linear ...
0
votes
1answer
31 views

How to simplify this logarithm?

I am looking at an example in my algorithms textbook, and I cannot seem to figure out how the following simplification occurred (my logarithm skills are a bit rusty): From this: ...
7
votes
1answer
89 views

Is there any explicit formula for $x_n$?

Let $a$ be a positive real number and $(x_n)$ be the sequence given by $x_1>0,$ $$x_{n+1}=\dfrac{1}{2}\Big(x_n+\dfrac{a}{x_n}\Big).$$ We can prove that $x_n\to\sqrt{a}$ as $n\to\infty.$ My ...
1
vote
0answers
32 views

How do I solve this recurrence relation and prove by induction?

I have this summation formula: $T(n)=\sum_{i = 1}^{n}T(n-i)T(i-1)$. Base case is $T(0)=1$, $T(1)=1$. How do I find the recurrence relation and prove it by induction?
1
vote
0answers
15 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 ...
0
votes
1answer
22 views

Explicit equation for recurrence relation

I have a recurrence relation: $A_{n} = -2A_{n-1} + 15A_{n-2}$ , with $a_{1} = 10$ and $a_{2} = 70$. This would be a linear homogenous recurrence relation of degree 2, right? Using the relation I ...
0
votes
1answer
34 views

Solving a Recurence Relation with 2 parameters

Given the following recurrence relation $$u(n,1) = 1$$ $$u(1,m) = 1$$ $$u(n,m) = u(n-1, m) + u(n, m-1)$$ with $n > 0, m > 0$, how can one end up with a closed formula, without using ...
2
votes
3answers
80 views

How to prove the following recursive sequence produce relatively prime numbers

Sequence an is defined recursively: $a_1 = 2$ $a_{n + 1} = {a_n}^2 - a_n + 1$ Prove that $a_i$ and $a_j$, $i \neq j$ are relatively prime. Hint: Prove that $a_{n + 1} = a_1 a_2 \ldots a_n + 1$ and ...
0
votes
1answer
14 views

Derivative of a second-iterate map

I have a homework problem I'm working on about the discrete logistic equation: $f(x)=rx(1-x)$ So far, through some experimentation and polynomial division I've dtermined that the fixed poits of ...
1
vote
2answers
34 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$ ...
2
votes
1answer
49 views

Solve the recurrence $T(n) = 2T(n-1) + n, T(1)=1, n\geq 2$

This question has been already solved here, I just want to figure out why I'm not being able to solve it using my method. Here's what I did - $T(n)=2T(n-1)+n$ $T(n-1)=2T(n-2)+(n-1)$ $\therefore ...
2
votes
0answers
147 views

How to solve this recurrence relation and solving the power series

Take the following recurrence relation into account: $$ a_{n+2} = \frac{1}{(n+1)(n+2)} \sum_{k=0}^n (s_k - (k+1)a_{k+1})(n-k+1)a_{n-k+1} $$ I know that: $$ s_{2m+1} = \frac{(-1)^m}{(2m+1)!} $$ and ...
4
votes
3answers
67 views

Stirling Numbers Proof

Prove the following: $$\sum\limits_{k=1}^{∞} (−1)^k (k − 1)! S(n,k) = 0$$ Where $S(n,k)$ is the Stirling numbers of the second kind. (Hint: Recurrence Relation) Workings: The recurrence relation ...
1
vote
4answers
30 views

Completing simplification step when solving a recurrence

I am trying to understand a simplification step in one of the recurrence examples solved by repeated substitution in a book of algorithms problems I found on Github. I am using it for extra practice ...
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
3answers
27 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
1
vote
2answers
27 views

Solving a recuurence relation

How can I solve the following recurrence relation? $f(n+1)=f(n)+f(n-1)+f(n-2), \ f(0)=f(1)=f(2)=1.$ I can use the characteristic equation which is $x^3=x^2+x+1$. It has three distinct roots ...
0
votes
1answer
42 views

Combinatorial Proof of Identity b_n

Prove that: $$b_n = 1 + \sum\limits_{k=1}^{∞} \binom{n-1}{k}b_k.$$ Workings: The first thing I noticed is that the above equation looks very similar to a Bell Numbers proof: ...
2
votes
2answers
68 views

Generating function for Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$. The initial conditions are $p_0 = 0$ and $p_1 = 1$. a) ...
0
votes
0answers
16 views

Proving a Recurrence Using Substitution

I am trying to understand an example of solving a recurrence using substitution (or unrolling it) in my book right now, but all of the steps do not seem clear to me. Here is the basic example: ...
1
vote
1answer
97 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
2answers
50 views

Induction proof concerning Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$, together with $p_0 = 0$ and $p_1 = 1$. Prove with ...