The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
3answers
36 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
2
votes
0answers
60 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
1
vote
2answers
142 views

Convergence and limit of a recursive sequence

Let $p>0$ and suppose that the sequence $\{x_n\}$ is defined recursive as $$ x_1 = \sqrt{p}, \quad x_{n+1} = \sqrt{p + x_n}, $$ for all $n \in \mathbb{N}$. How can I show that $x_n$ converges, ...
1
vote
0answers
23 views

recursive definition produces different sequence than non-recursive

I had a homework problem where I had to give a recursive definition for the sequence $$a_n = n(n+1)$$ Which produces {2, 6, 12...}, so I first came up with this (I'll call it answer 1): $$a_{n+1} ...
2
votes
0answers
70 views

How to get the period of oeis.org/A130166 other than by trail?

oeis.org/A130166 a(0)=1; a(n)=prime(mod(a(n-1),1000)) starts with: ...
3
votes
1answer
72 views

Recursively deleting every second element in a list

This question got me thinking. If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any ...
5
votes
1answer
70 views

Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why?

I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. ...
1
vote
3answers
163 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
0
votes
2answers
55 views

Understanding second axiom of Primitive recursion

I read about Primitive recursion and was able to understand most of it. However I am finding it very difficult to understand the second axiom of primitive recursion. I can make out that it helps in ...
4
votes
5answers
831 views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
0answers
22 views

Expressing three recursive forms into one using parameters?

I have the following recursive function that takes three forms and I want to express it in one form: Initial: $f(x) = m * f(x-1)$, $f(0) = value.$ Forms: 1 - $f(t) = m * f(t-1)$. where t is at ...
0
votes
3answers
34 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
0
votes
1answer
31 views

Time complexity of indirect recursion

How to find the complexity of an the given algorithm: Algorithm f(int n) { if(n==1)return(1); else { f(n-1)+g(n-1); } } Algorithm g(int n) { ...
2
votes
1answer
76 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
1
vote
1answer
36 views

Function composition in computability

I have been reading Cutland's computability book, which is really good! However, I have found myself thinking way too much about one little passage in the the third section of the second chapter (the ...
0
votes
3answers
47 views

A multivariate function, computable for any fixed first argument, is computable

Claim: If $f:\mathbb N^{k+1}\to\mathbb N$ is a function such that for all $x_0\in\mathbb N$, $\lambda x_1,\dots,x_k.f(x_0,x_1,\dots x_k)$ is a partial recursive function then $f$ is also partial ...
0
votes
1answer
48 views

Recursive Definition Theorem

I found two versions of a theorem which guarantees that recursive defined functions do exist (or that recursive definitions do make sense). The first is: Given a function $f:X\to X$ and an element ...
0
votes
3answers
112 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
0
votes
1answer
14 views

xyplus recursive language

For {x, y, +}, the language XYPlus is shown recursively as: (1) x and y are in XYPlus . (2) So if a and b are words in XYPlus ...
0
votes
1answer
49 views

Mathematical Induction Recursion

Consider the recursion given by $f(n) = 2f(n−1)− f(n−2)+6$ for $n ≥ 2$ with $f (0) = 2$ and $f (1) = 4.$ Use mathematical induction to prove that $f (n) = 3n^2 −n+2$ for all integers $n ≥ 0.$
1
vote
2answers
84 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
2
votes
2answers
163 views

Proving a recurrence relation for strings of characters containing an even number of $a$'s

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings. ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
3
votes
1answer
99 views

How many arrangements of the digits 1,2,3, … ,9 have this property?

How many arrangements of the digits 1,2,3, ... ,9 have the property that every digit (except the first) is no more than 3 greater than the previous digit? (For example, the arrangement 214369578 has ...
0
votes
0answers
51 views

Can the method of generating functions be applied to linear recursions of order $>4$?

I just got in touch with the method of solving recursions with generating functions. However, even if it is not mentioned anywhere, it seems to me, this approach is not applicable for recursions of ...
2
votes
3answers
94 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
0
votes
0answers
47 views

How can I find the distribution of a recursive relation with two parameters?

Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also ...
0
votes
1answer
38 views

Find a formula for a sequence of the following character strings

Given strings: 0, 020, 0208020, 0208020180208020, 0208020180208020320208020180208020, ... I have to write a C++ program that computes the nth string. My problem is ...
3
votes
1answer
128 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
13
votes
4answers
485 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1]\,$ satisfying $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the functional relation $$ f\big(2x-f(x)\big)=x, \tag{1} $$ for all ...
0
votes
1answer
45 views

Master's theorem applicability.

I have to find out if the following recurrence can be solved with the master theorem: $$T(n) = 3T\left(\frac{n}{2}\right) + n^{\log\log n}$$ I have figured that, here, I have the third case because ...
3
votes
1answer
35 views

Can you prove this recursive multiple $n$-sided dice throwing statement?

Let $W_{s,r,n}$ be the total number of ways that the sum $s$ can be displayed after throwing $r$ number of $n$-sided dice. Define $$W_{s,0,n} = \begin{cases} 1, & \text{if s = 0} \\ 0, & ...
2
votes
2answers
68 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
4
votes
0answers
157 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
1
vote
1answer
36 views

Maths/Programming recursion question

I know this is a programming question but it seems to be more on the mathematical side ( recursion ) I was hoping someone would be able to explain it to me since it will probably be on my exam ...
3
votes
4answers
123 views

Proving convergence of a sequence

Let the following recursively defined sequence: $a_{n+1}=\frac{1}{2} a_n +2,$ $a_1=\dfrac{1}{2}$. Prove that $a_n$ converges to 4 by subtracting 4 from both sides. When I do that, I get: ...
0
votes
2answers
29 views

Express recursive funtion in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
1
vote
1answer
57 views

On the size of a set of functions such that $f(i)\ne f(i+1)$ for every $i$ (and similar conditions)

For a finite set $A$,let $|A|$ denote the number of elements in the set $A$. (a) Let $F$ be the set of all functions $$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying ...
3
votes
1answer
55 views

Structure of partial recursive function over recursively enumerable guard

I read that the function $$ f(n) = \left\{ \begin{array}{l l} g(n) & \quad \text{if $n \in A$}\\ \text{undefined} & \quad \text{otherwise} \end{array} \right. $$ is recursive if ...
0
votes
1answer
27 views

computer recursion same question but omitting defdef

Given the alphabet {a,b}, give a recursive definition for the language whose words don't contain the string aa. My solution is i) b ∈ L1 ii) if w ∈ L1, then so is wba, abw My question is should i ...
1
vote
1answer
46 views

Another recursive math question

Given the alphabet {def ghi}, give a recursive definition for the language whose words contain the string defdef. My solution is: i) def ∈ L and ghi ∈ L ii) if u = def and w ∈ L*, then so is uu, ...
0
votes
1answer
44 views

recursive definition of strings

I have been unable to find any examples that resemble this problem and I am having issues with recursion. Here is the problem: Give a recursive definition for the set of strings of letters a, b, c, ...
0
votes
2answers
57 views

Recursive definition attempt.

I have the following question: $\text{b) }$Give a recursive definition for the function $f:\Bbb N\to\Bbb N$ which calculates the following sum for any $x\in\mathbb N$: ...
1
vote
1answer
48 views

computer theory recursion

I am having a bit of trouble understanding recursion and would like a bit of guidance. Consider the recursively defined language, L1: i) x ∈ L1 and y ∈ L1 ii) if w ∈ L1, then so is wxw ∈ L1 I have ...
2
votes
3answers
51 views

Recursion definition

Give a recursive defintion of the following set: $\{ 5^m 7^n \mid m, n \in N \}$ I don't have the slightest idea how to approach this question, id be really grateful if someone could provide me with ...
-2
votes
1answer
37 views

Proof by induction help

I don't know the full process of induction, as it's one of the harder questions on my upcoming test papers I thought i'd attempt to get a basic understanding; in order to get a 1/2 marks out of the ...
0
votes
2answers
50 views

proof by induction question

I decided to try proof by induction without any help = ) so if someone could check it out, pretty sure it's unfinished or, well i'm not sure. Also, if possible, could you take a logical guess for how ...
0
votes
1answer
49 views

function proving with induction [closed]

I'm having trouble with the following past paper question : Consider the function $take: \Bbb N \to \Bbb N$ defined recursively as follows: Base case: $take(0) = 100$ Recursive case: ...
0
votes
2answers
28 views

Recursion function question again

http://vvcap.net/db/3RxO1KX2d4LxgD714Tyh.htp mult(x,y)= mult(x-1,y)+4 mult(0,4)=0 mult(1,4)=mult(0,4)+4 mult(2,4)=mult(1,4)+4 mult(3,4)=mult(2,4)+4 I'm not sure whether this is correct, but i think ...
0
votes
0answers
30 views

Closed form for a special recursion?

Does the recurrence relation $$ a(n+1) = a(n)^2 + 1,\quad a(1)=1, $$ have a closed form solution? I have tried hard to find it, but failed. Any ideas ? I am particular interested in prime ...