Tagged Questions

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

learn more… | top users | synonyms

0
votes
2answers
54 views

If $ i=0.09 $, find $ n $ and the amount of final payment.

A fund of $ \$500 $ is to be accumulated by $ n $ annual payments of $ \$100 $, plus a final payment as small as possible made one year after the last regular payment. If $ i = 0.09 $, find $ n $ and ...
4
votes
5answers
315 views

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
1
vote
1answer
72 views

Explicit formula for recurrence relation with $A_{N+1}= A_N+{(2/7)}^N$

How can I find a non-recursive formula for the sequence $A_N$ when the sequence is defined as $A_1=1$ and for $N\ge 1$, $A_{N+1}= A_N+{(2/7)}^N$?
3
votes
1answer
75 views

Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

I want to solve the following recurrence: \begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation} What are some basic "methods" I can use to guess a ...
3
votes
1answer
41 views

Is there a general formula for recurrence relations like $ f(x+1) = \sum_{i=0}^k a_n{[f(x)]}^n $

Or in other words, polynomial relation of the function rather than the argument. I've worked out that in general $ f(x+1)={f(x)}^n $ implies $$f(x) = C^{n^x} $$ for some C, but I would like to know if ...
4
votes
1answer
117 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
3
votes
2answers
124 views

Systems of recurrence relations

This is homework, please only provide hints! I have a question: Given a 1-by-n board, let $a_{n}$ denote the number of ways to color the board with red, blue, white and green where that the number of ...
2
votes
1answer
569 views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + ...
2
votes
1answer
113 views

Show that Fermat number $F_n$ and its index $n$ are coprime.

I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this? I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
1
vote
2answers
102 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
3
votes
0answers
102 views

How to resolve this equation for f(n) without using f(n-1)

I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
3
votes
1answer
162 views

Issue while applying Master Theorem

I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
1
vote
2answers
83 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
0
votes
1answer
743 views

solving recurrence relation by substitution method and find asymptotic bound

Solve the following recurrence relations and give a bound for each of them. $T(n)= 2T(n-3)+1$ $T(n) = 5T(n-4)+n$
0
votes
1answer
82 views

A Recurrence relations of the form: $T(n) = aT(\frac{n}{b}) + f(n)$

Is there a name / terminology used for describing the above type of recurrence relation? Is there a general method for finding a closed form for these types of recurrences? When does a closed form ...
2
votes
4answers
440 views

Solving Recurrence T(n) = T(n − 3) + 1/2;

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$ I tried solving it using the forward iteration. $$\begin{align} T(3) ...
0
votes
1answer
45 views

Predictions for recurrence relations

Given the recurrence relation $a_n = 2a_{n-1} + a_{n-2}$ $a_0 = 1$ and $a_1=1$ Is it true that $a_n < 6a_{n-2}$ for all $n\ge4$ I'm not really sure how to go about solving this problem. I've ...
20
votes
4answers
508 views

Evaluating $\sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}}$

Inspired by Ramanujan's problem and solution of $\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + \ldots}}}$, I decided to attempt evaluating the infinite radical $$ \sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}} ...
0
votes
1answer
56 views

solving recurence relations

$i a_i = \left(i + 1\right) a_{i-1} + 2(i - 1)$ where $a_0 = a_1 = 0$ Solving this recurence relation. How can I do this ? I tried to make something like $i (a_i + 2(i-1)) = (i+1) (a_{i-1} + 2 ...
2
votes
2answers
118 views

When is a linear recurrence relation solvable?

I was reading this definition of a linear recurrence, and was wondering what characteristics are required of a linear recurrence for it to be solvable? Meaning, can I find a closed form? The subject ...
1
vote
1answer
253 views

finding recurrence relations

This is homework, please only provide hints. I've been given a problem: consider a 1-by-n chessboard. Coloring each square with one of two colors, red or blue. Let $a_n$ be the number of colorings in ...
0
votes
2answers
132 views

General term of $a_n = 2a_{n-1} + 1$ [duplicate]

Find the general term of the sequence defined by: $a_n = 2a_{n-1} + 1$ where $a_1$ is given Thank You
7
votes
0answers
84 views

Properties of a continued fraction convolution operation

Usually the partial numerators of a continued fraction are all 1s. Has anyone considered the operation where you convolve 1 continued fraction with another, in other words, make a new continued ...
0
votes
2answers
109 views

Solving for a Generating Function in a Special Case

I'm trying to teach myself about generating functions by following this text. I've hit a stumbling block in one of the exercises left for the reader (Sec. 1.4), which I'd quite like to resolve before ...
1
vote
1answer
123 views

Solve recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1)

$T(N) = N + T(N-3)$ This is what I got so far $$\begin{align}&= T(N-6) + (N-3)+N\\ &= T(N-9) + (N-6) + (N-3)+N \\ &= T(N-12) + (N-9) + (N-6) + (N-3)+ N\end{align}$$ I think I should use ...
2
votes
2answers
250 views

How do you find the closed form of these recurrence relations?

I found these two recurrence relations in an old textbook and was hoping someone could show me how to solve them for their closed form. If not, a final answer would also be appreciated, as it helps ...
2
votes
1answer
154 views

Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
1
vote
2answers
4k views

Recurrence - finding asymptotic bounds for $T(n) = T(n-2) + n^2$

I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence ...
2
votes
0answers
67 views

How much information do I gain from each modular inequality?

Problem details: Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants. Furthermore let $f(x) = a x + b \pmod{p}$ and let the value $r_k$ be defined by the first-order recurrence ...
4
votes
2answers
124 views

Does this problem have a name?

Recently our lecturer told us that it is an unsolved mathematical problem if the following while loop aka iteration ever terminates. Unfortunately I forgot to ask him what it is called. If someone ...
0
votes
1answer
10 views

Given the solution of a RR, how can we find the BIG-O complexity?

Suppose we have the solution to a recurrence relations as $c^n+n(\log(n))^2+(10n)^c$. How can we determine the BIG-O complexity if we say that $c > 1$?
1
vote
1answer
85 views

Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
0
votes
3answers
75 views

Still stuck on recurrence

I am still stuck on this problem and it is very frustrating. I need to solve this using exponential generating series and again with telescoping. Problem is I am not even sure what telescoping is and ...
4
votes
1answer
486 views

Finding recurrence relations in combinatorics

I'm working my way through basic combinatorics questions with recurrence relation, and can't quite get my head about the right way of solving them. For example, I have two following examples in my ...
0
votes
2answers
240 views

Trying to find a recursive solution to an infinite series

I have an infinite series that I need to write a function for (in Python) to calculate. To do so, I need to find the recursive definition of the formula, which I am having trouble with. ...
1
vote
1answer
77 views

Recursive functions, successor function

How to show that the power function $\displaystyle A=2^{m^2}$ is primitive recursive based on successor function? Thanks much in advance!!!
2
votes
2answers
82 views

Help solving summation series of a recursive function

Yesterday in class, we were analyzing the Karatsuba multiplication algorithm and how it applies to recurrence equations. Time ran short, and I feel I missed how to solve the final summation. First, ...
0
votes
1answer
93 views

What is the closed form for the general recurrence relation?

$T(N) = a\cdot T(N-b) + c \cdot N + d $ $T(0) = 0$ I honestly don't understand this concept at all. Any help would be great.
2
votes
3answers
146 views

Solve the recurrence $y_{n+1} = 2y_n + n$ for $n\ge 0$

So I have been assigned this problem for my discrete math class and am getting nowhere. The book for the class doesn't really have anything on recurrences and the examples given in class are not ...
0
votes
1answer
42 views

How can I prove a sequence of values follows a certain closed form equation?

For example, imagine I'm trying to do this $$ (1-3x+3x^2)/(1-3x+3x^2-3x^6) = \sum\limits_{n=0}(a_nx^n) $$ $$ (1-3x+3x^2) = \sum(a_nx^n) * (1-3x+3x^2-3x^6) $$ Then say we are given some closed ...
2
votes
1answer
65 views

Recurrence relation help

The function $\psi_k(n)$ satisfies the recurrence relation: $$\sum_{j=0}^k\binom{k}{j}(-1)^j\psi_j(n)\ln(n)^{k-j}=\psi_k(n)$$ Using this, is there a general way I can re-write the function $ ...
2
votes
2answers
306 views

Solving recurrences with boundary conditions

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of. Consider this problem: Show that ...
1
vote
2answers
408 views

Find a formula for the nth term of the sequence defined by the third-order recursion:

$t_{n+2} = 3t_{n+1} + 6t_n – 8t_{n–1}$ with initial values $t_0 = 3, t_1 = t_2 = –6$ You don't have to give me the answer, please just try and point me in the right direction.
1
vote
3answers
97 views

Can a recurrence relation have more than one exact solution?

Can a homogeneous linear second degree relations with constant coefficients have more than one exact solution? Consider the following $T(n) + aT(n - 1) + bT (n - 2) = 0$ Some equations of this form ...
2
votes
2answers
221 views

Question about theta of $T(n)=4T(n/5)+n$

I have this recurrence relation $T(n)=4T(\frac{n}{5})+n$ with the base case $T(x)=1$ when $x\leq5$. I want to solve it and find it's $\theta$. I think i have solved it correctly but I can't get the ...
2
votes
2answers
68 views

Integral expansion help!

So I'm very close to finishing a proof of the exponential function in terms of differential equations. For this next step, I have to show the following. For $n \ge 0$ define $E_n (t)$ recursively ...
2
votes
0answers
54 views

how to compute $\lim_{n\to\infty}\ln(f(n))/\ln(n)$ for this given $f(n)$?

Let $c=f(0)$ be a real number and $n,m$ positive integers. Let $P_k(n)$ be integer polynomials of $n$. Let $f(n)$ be defined by the recursion $\left[\sum_{k=0}^{m} P_k(n)f(n+k)\right]+P_{-1}(n)=0$. ...
0
votes
3answers
186 views

Power series and recurrence

Please help me find the radius of convergence and the value of the following power series: $\sum_{n=0}^{\infty} a_nz^n$, when $a_0=1,a_1=-1$, and $3a_n+4a_{n-1}-a_{n-2}=0$ for $n>1$.
3
votes
5answers
777 views

Limit for a Recurrence Relation

How I can find a limit for this recursively defined sequence? $$a_0>0, a_{n+1}=\frac{a_{n}+2}{3a_{n}+2}$$ I'm particularly interested in answers involving concepts like contractive sequences and ...