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

learn more… | top users | synonyms

3
votes
2answers
36 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
1answer
26 views

How do I solve this recurrence relation

How do I solve the following recurrence relation: T(n)=4T(n-1) - 3T(n-2) I tried using substitution but failed as I was unable to find any "general" i-th term ...
3
votes
3answers
122 views

Closed Form of Recursion

Given that $a_0=2$ and $a_n = \frac{6}{a_{n-1}-1}$, find a closed form for $a_n$. I tried listing out the first few values of $a_n: 2, 6, 6/5, 30, 6/29$, but no pattern came out.
1
vote
1answer
14 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
0
votes
1answer
20 views

Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
0
votes
0answers
10 views

count the permutation which have $k$ maxima

I need some help for the following homework question. A permutation $P (\pi_1\pi_2...\pi_n)$ of {$1,2,...,n$} is given. We say that $j$ is a maxima of $P$ whenever $\pi_j$>$j$. How can I find ...
-1
votes
1answer
40 views

How do I compute this recurrence relation? [on hold]

I run into this recurrence relation while I'm doing my research, and I can't solve it. Is there anyone who can give me ways to do this? $\sum_{i=1}^{\infty}\pi_i = 1$ $p^2 \pi_i = \{(1-p)^2 + ...
1
vote
1answer
26 views

$g(n)=\sum_{i=0}^{n-1}g(i)g(n-i-1)$, and $g(0) = 1$, so which is $g(n)$?

I have an equation that: $g(n) = g(0)g(n-1)+g(1)g(n-2) + ... + g(n-2)g(1)+g(n-1)g(0)$ And I also know that $g(0)=1$. How can I derive the close form of function $g(n)$ ?
1
vote
2answers
226 views

Help solving a recursion function T(n) = T(n-2) +3

I have the following recursion function: $T(1) = 0$ $T(n) = T(n-2) + 3$ where n is odd integers I know the closed form of this is: $T(n) = \frac{3n-3}{2}$ but this was purly by guessing. Is it ...
0
votes
1answer
17 views

Number of sequences with n digits, even number of 1's (Continued question)

Some guy asked a very interesting question here before. He was trying to figure out a formula to calculate $a_n$ number of sequences with n digits from $\{1,2,3,4\}$ and an even number of 1's. Which ...
1
vote
2answers
17 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
0
votes
1answer
58 views

Gambler's ruin and coin toss

Edit 3. Fixed question to be more clear and include current solution Problem Two players player 1 and player 2 plays a game of fair coin flipping. Player 1 starts with $A$ coins and Player 2 with ...
2
votes
5answers
24 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
0
votes
1answer
16 views

recursive definition of the relation

Give a recursive definition of the relation greater than on N X N using the successor operators s? I answered this question throw this way: Basis: o ∈ N X N recursive step: if n ∈ N X N, then s(n) ∈ ...
0
votes
1answer
21 views

Prove boundedness of recurrence relation

For a number sequence $\{y_n\}$ we know that $y_{n+1} = 2y_n-y^2_n$ If: $0<y_0<1$ show that $0<y_n<1$ for all integers $n>0$ I've tried solving the recurrence relation, but I couldn't ...
0
votes
1answer
25 views

recursive sequence - Which approach can I take to solve this equation?

Having this recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 4·3^n$ $a_1 = 36$ $a_0 = 0$ How can I solve this? I tried by characteristics roots and got stuck: *making $a_n=r^n$ $r^n = 5r^{n-1} - ...
2
votes
3answers
82 views

Solving a recurrence relation of second order

I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$ $x_2 = 2(x_1-x_0)+x_1$ $\begin{align} x_3 = ...
0
votes
2answers
42 views

Closed form formula for the given product

I'm working on a recurrence which give me the following solution: $$ f(n)=(2+1)(2+\tfrac12)(2+\tfrac13)\cdots\left(2+\tfrac1{\lg(n)}\right) $$ so for $n=16$, $f(n)$ is just like: $$ ...
2
votes
1answer
57 views

Solving the recursion $y_n=2ny_{n-1}$ with Wolfram|Alpha

This is blowing my mind away ... this should be easy stuff! Starting with the recursive formula $y_n=2n*y_{n-1}$ where $y_1=5.$ I'm trying to come up with a formula for the series { 5, 20, 120, 960, ...
1
vote
1answer
27 views

Exponential growth with a constant

Some guy opens a bank account with an initial amount of $\$1,000$. Each month he deposits $\$200$ and the bank gives him a monthly interest of $6\%$. I want to find the closed formula. Given this, we ...
2
votes
1answer
37 views

Unsolveable equation?

If we have the inhomogenous recurrence relation $$f(n+2) - 6f(n+1)+9f(n) = 6*3^{n} + 2^{n} = 2 * 3^{n+1} + 2^n, f(0) = 0, f(1) = 1, n \ge 1$$ Step 1: Find the homogenous solution $f(n) = C_13^n + ...
2
votes
1answer
37 views

Proof of convergence of $a_{n+1} = \dfrac{a_n^2 + 1}{3}$ in $\mathbb{R}$ and finding its limit

I'm starting a class on Advanced Mathematics I next semester and I found a sheet of the class'es 2012 final exams, so I'm slowly trying to solve the exercises in it or find the general layout. I will ...
2
votes
1answer
59 views
+50

Recurrence vs Recursive

Say team 1 is studying the recursive characteristics of a function. Team 2 is studying the recurrent characteristics of the same function. Are the 2 teams studying the same thing? I have found for ...
0
votes
1answer
18 views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
3
votes
5answers
104 views

Solve $ x_{n+1} - x_n = 2n + 3$

Solve $$ x_{n+1} - x_n = 2n + 3, x_0 = 1, n \ge 0$$ I would try to find a homogen solution and used $$ r^2 - r = 0$$ and got $$x^h_n = A1^n$$ but this seems wrong and I'm stuck on how to continue. ...
0
votes
0answers
72 views

Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n

(a) Let Cn denote the number of ways of writing a valid list of open and closed parentheses of length 2n (valid means that at any point along the list, the number of open parentheses must be greater ...
0
votes
2answers
21 views

What is the intuitive idea behind looking for a solution of the form an=r^n for a linear homogeneous recurrence relation?

In my textbook, under solving linear homogeneous recurrence relations, it says that the basic approach for solving them is to look for a solution of the form an = rn, which yields the characteristic ...
1
vote
2answers
18 views

Recurrence Problem involving multiple dependencies.

I have 3 equations :- $r_n=r_{n-1}+5m_{n-1}$ $m_n = r_{n-1} + 3m_{n-1}$ $p_n = 5m_{n-1}$ The initial values of the sequences are $$r_0=3, m_0=1, p_0=0$$ How can I get the formula to get the nth ...
0
votes
0answers
54 views

Substitution method for solving recurrences

I'm having issues understanding how to solve recurrences via the substitution method. From what I understand, I need to guess the form of the solution first and then use induction to prove that the ...
0
votes
1answer
23 views

limit of $f_n(a) = a^{f_{n-1}(a)}$ as $n$ approaches infinty for small values of $a$

So a friend started, in boredom, calculating values of what I have formalized as $f_n(a) = a^{f_{n-1}(a)}$ (also $f_0(a)=a$) for $a = 1.1$. He noticed that on his calculator it was not changing value ...
0
votes
0answers
11 views

A question on bivariate recurrence

Is there a way to get a closed form of this recurrence (albeit approximate): $$A(n ,k ) = {1 \over {d^k}}A(n-1, k-1) + (1 - {1 \over {d^k}})A(n-1,k)$$ Where, $n,k \ge 0$ and $d \ge 2$ are integers. ...
0
votes
0answers
29 views

Solving Recurrence Relations (Nonlinear?)

I'm not sure the term, but how do you solve a recurrence relation with a multiplicative factor in the index, so as opposed to $a_n=a_{n-1}+a_{n-2}$ we have something like $a_n=a_{\frac{n}{2}}$. I know ...
0
votes
1answer
22 views

How many partitions are there?

How many partitions are there for $\{1,\cdots,100\}$ for $3$ sets, $A,B,C$, such that $A$ cannot contain consecutive numbers ($\left|a-b\right|=1$) Anyway, I thought about using recurrence ...
1
vote
1answer
38 views

Limit of a recursive function

I have a recursive functoin: $$\log^{'}(n) = \begin{cases} & 1 \text{ if } n \leqslant 1 \\ & 1 + log^{'}(\log(n))\text{ otherwise} \end{cases}$$ This function grows VERY slowly. Is this ...
2
votes
1answer
25 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...
0
votes
1answer
79 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where Cn denotes the number of ways of writing a valid list of open and closed parentheses of length ...
0
votes
1answer
48 views

The solution of recurrence $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$ is $O(n\lg n)$

Given, $T(n) = 2T(\lfloor{n/2}\rfloor + 17) + n$. Show that the solution to T(n) is $O(n\lg(n))$. Here's what I tried - Assumption: $T(\lfloor n/2 \rfloor) \le c(\lfloor n/2\rfloor + 17)\cdot ...
1
vote
1answer
42 views

Segner's Recurrence Relation [closed]

Why is Segner's Recurrence Relation formula valid. Does anyone know how to prove it? I can't seem to understand why this formula works/is true. $$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots ...
1
vote
1answer
35 views

How do I create a function from this code? [closed]

Here is the code: for (int i = 1; i < n; i *= 2) ++k; I need to express this as a function. I don't know where to begin.
1
vote
2answers
37 views

$n$th derivative of $e^{-x^2}$

I observed that $f^{(n)}(x)= \begin{cases} e^{-x^2} & \text{if $n=0$}\\ -2xe^{-x^2} & \text{if $n=1$}\\ f^{(n-1)}(x)-f^{(n-2)}(x) & \text{otherwise.} \end{cases}$ How to get the closed ...
1
vote
1answer
52 views

Properties of a recursively-defined sequence using induction

This is a homework problem. Not expecting the solution, just a nudge in the right direction! $N$ is a function defined inductively as follows: $$N(1) = N(2) = N(3) = 1$$ $$N(n) = N(n−1) + N(n−3) ...
0
votes
1answer
41 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
2
votes
2answers
46 views

Help with a recurrence relation

I have been battling with the following: $$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$ I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving ...
0
votes
1answer
27 views

Why does the sign change here?

They give the recurrence relation as: $$T(n) − 4T(n − 1) + 3T(n − 2) = 0,\ T(0) = 0,\ T(1) = 2$$ And then they say it can be written as the following for $n > 1$: $$T(n) = 4T(n − 1) − 3T(n − 2)\ ...
1
vote
2answers
34 views

Help with proof by induction

The author generates a Tower of Hanoi and looks at the sequence: $$1, 3, 7, 15, 31, 63,...$$ He guesses the recurrence relation from the first few terms: $$H_{n} = 2^{n} - 1$$ Now he wants to ...
1
vote
3answers
42 views

recurrence relation of a finite sequence

Suppose I have a sequence of vectors $v_1,v_2,\ldots,v_n$ and for $k=1,2,\ldots,n-2$ $$v_{k+2}=av_{k+1}+bv_k, \quad a,b\in \mathbb R.$$ Can I deduce that $v_{k}=Ax_1^k+Bx_2^k, k=1,2,\ldots,n$ in which ...
1
vote
0answers
12 views

Is there a way to express a closed form for a partial derivative of this recurrence relation?

Here's the relation: if $n\ge j:$ then $$ \sigma(n,j,d) = d \cdot\left( \log j-\sigma\left(\frac{n}{j}, 1+d, d \right)\right)+\sigma(n, j+d, d )$$ And here's the terminating condition if $n < j$ ...
2
votes
1answer
28 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
1
vote
2answers
71 views

How does this simplification work?

The following recursive function was given: $$T\left(n\right) = T\left(n - 1\right) + x$$ The author stated that by using repeated substitution we can solve the recurrence relation: The basic ...
1
vote
1answer
21 views

Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?