The tag has no wiki summary.

learn more… | top users | synonyms

-4
votes
1answer
37 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
-2
votes
0answers
30 views

Discrete Mathematics Recursion Question [on hold]

Function $f$ is defined recursively by $f(0)=f_0, f(1)=f_1$, and $f(n+2) = f(n)+f(n+1)$ for $n \geq 0$. (a) For $n \geq 0$, let $c(n)$ be the total number of additions for calculating $f(n)$ using ...
1
vote
2answers
63 views

Definition by Recursion: why is the existence part not (almost) obvious?

I saw the following statement. Let $H$ be a set, let $e\in H$ and let $k:H\rightarrow H$ be a function. Then there is a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that ...
0
votes
0answers
47 views

Kleene's recursion theorem

Would anybody be able to provide me (someone with little familiarity with the subject matter) with a bit of background to the Recursion Theorem and guide me towards some texts on its mathematical and ...
0
votes
0answers
125 views
+50

Differend kind of recursion.

How are called these special case of definition by recursion? given increasing $f,g: \Bbb {N} \rightarrow \Bbb N$ and $b,b_1,b_2 \in \Bbb N$ 1 (a special case of primitive recursion) ...
1
vote
1answer
19 views

How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically. Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: ...
2
votes
2answers
25 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
3
votes
4answers
39 views

Is this a correct recursive sequence definition?

Take this definition: Is this definition of $s_k$ for $k\ge2$ correct? $s_k=6a_{k-1}-5a_{k-2}$ but where does the $a$ term come from? The book swaps $a$ and $s$ interchangeably.
0
votes
2answers
13 views

Recursion, Explicit Equasion

Prove $\ a_{n}<2^{n} $ for every natural number n, where $\ a_{n} $ is defined recursively by $$ a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$$ Once I get the explicit ...
0
votes
2answers
41 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
40 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
1
vote
0answers
31 views

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be ...
2
votes
1answer
50 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
0
votes
1answer
17 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
0
votes
1answer
17 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
0
votes
1answer
24 views

How to deduce from a recursive variant of the triangular numbers the non-recursive form?

This is probably simple (if not, my apologies beforehand), but I have the following formula: $$f(0) = 2$$ $$f(x) = 6x + 2 + f(x -1) \; \text{ where } x \in \mathbb{N}_{\gt 0}$$ The formula actually ...
2
votes
0answers
57 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
1answer
25 views

proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
0
votes
1answer
27 views

Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I ...
0
votes
0answers
16 views

Structural induction question?

The question is: Give recursive definition of a set "S" of all binary strings starting with a 1. Do the three steps: base, recursion, and restriction So far, I have: base: empty string recursion: ...
-1
votes
1answer
49 views

Proof of a sequence with recursion

The problem asks to prove the following to be true. $$F^2_{n+1} - F_{n+1} F_n - F_n^2 = (-1)^n$$ Anyway, I've tried looking at this or similar proofs for going on an hour now, pretty much the only ...
1
vote
2answers
21 views

Question over recursive definitions

Let $E$ be the set of even integers. Then the Base Case: $0\in E$ And the constructor case would be If $n \in E$ then so are $n+2$ and $-n$. This makes sense. But would the Base case and constructor ...
-1
votes
0answers
29 views

How To Solve the recursion?

Need help with the following recursion: $$T(n)=2T\left(\frac n2\right)+ \frac n{\log n} $$ I Tried to solve it to no avail, and the master theorem doesn't seem to work on it. Thanks
2
votes
5answers
59 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
3
votes
2answers
40 views

$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$ $0<c<1$ and $T(1)$ is constant. My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong. My guess is that $T(n) = ...
0
votes
1answer
40 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
0
votes
1answer
29 views

Discrete Math Recursive Functions for Strings

Recursive Functions for Strings Construct a recursive definition for the following string function over the alphabet {x,y}: f(x) returns the string where every x is replaced by xy and every y is ...
0
votes
0answers
23 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
4
votes
3answers
153 views

Definition of General Associativity for binary operations

Let's say we are talking about addition defined in the real numbers. Then, by induction we define $\sum_{i=0}^{0}a_i=a_0$ and $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ for $n> 1.\:$ Now, how do ...
0
votes
2answers
48 views

Prove via induction this recursively defined sequence

Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$ Highly verbose solutions are greatly appreciated.
2
votes
1answer
116 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
0
votes
1answer
28 views

Show that the set of sets {$A_n$} has $n$ elements and that it is transitive

We define by recursion the set of sets {$A_n : n∈ℕ$} this way: $A_0 = ∅$ $A_{n+1} = A_n ∪$ {$A_n$}. I want to prove by induction that for all $n∈ℕ$, the set $A_n$ has $n$ elements and that $A_n$ ...
0
votes
2answers
81 views

Prove that a Fibonacci number is greater than $ φ^n$

How can I prove the following: If $f_n$ is a number of the Fibonacci sequence and φ= $\frac{1+\sqrt{5}}2$, then $f_n > φ^n$ for every $n >2$? I have tried using induction but I can't ...
0
votes
2answers
29 views

What is the general stragety for conjecturing a formula based off a pattern?

Is it simply to guess and evolve a answer until it gets closer or is there an approach? Ex: Find the formula for: $a_k = \frac{a_{k-1}}{2} + 1$ where $a_0 = 1$. One would go: $a_1 = 3/2, a_2 = ...
0
votes
1answer
18 views

How do you use induction on a recursive sequence using different variables?

I've been working on some recursive sequences for my Discrete class. I've understood most of them, but I've come to a new question which I'm confused about. A sequence $C_{0}$, $C_{1}$, $C_{2}$ is ...
0
votes
3answers
29 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
55 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
91 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
21 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} ...
1
vote
0answers
62 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
56 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
65 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
92 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
51 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
557 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
21 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
31 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
24 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
69 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
29 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 ...