Find a recurrence relation from a sequence of integers

Click For Summary
SUMMARY

The discussion focuses on deriving a recurrence relation from a sequence of integers defined as An = xn + yn, where x and y are integers and n is a non-negative integer. Participants explore the challenges of expressing An+1 in terms of An, noting that the terms raised to different powers complicate the translation. The conversation also touches on solving standard recurrence relations of the form An+2 + pAn+1 + qAn = 0 and the conditions under which solutions take the form An = Bxn + Cyn.

PREREQUISITES
  • Understanding of integer sequences and their properties
  • Familiarity with recurrence relations and their solutions
  • Knowledge of polynomial expressions and their manipulation
  • Basic concepts of linear algebra as applied to sequences
NEXT STEPS
  • Study methods for solving linear recurrence relations with constant coefficients
  • Learn about characteristic equations and their role in finding solutions
  • Explore generating functions as a technique for analyzing sequences
  • Investigate specific examples of integer sequences and their recurrence relations
USEFUL FOR

Mathematicians, computer scientists, and students studying discrete mathematics or algorithm design who are interested in understanding and solving recurrence relations.

swtlilsoni
Messages
16
Reaction score
0
If you are given a sequence of integers such as:
An=xn+yn
where x and y are integers. and n=0,1,2,3...
how would one find the recurrence relation?

I tried writing An+1 in terms of An but it doesn't come out neatly because it doesn't translate so well. And there are terms raised to the n+1 multiplied by terms raised to the n. Am I going about it the wrong way?
 
Physics news on Phys.org
hi swtlilsoni! :smile:

i assume you know how to solve recurrence relations such as An+2 + pAn+1 + qAn = 0 ?

ok, then when will it have solutions of the form An = Bxn + Cyn ? :wink:
 

Similar threads

Proving that a recurrence holds for all n
  • · Replies 11 ·
Replies
11
Views
2K
What is the recurrence relation for strictly increasing sequences from 1 to n?
  • · Replies 3 ·
Replies
3
Views
3K
How Do You Find a Recurrence Relation for a Power Series Solution of an ODE?
  • · Replies 8 ·
Replies
8
Views
3K
Differential Equation - Series - Recurrence Relation
  • · Replies 2 ·
Replies
2
Views
2K
Combinatorics - Recurrence Relation Question
  • · Replies 4 ·
Replies
4
Views
2K
Recurrence relations with rabbits pairs
  • · Replies 8 ·
Replies
8
Views
3K
How to find upper bound for recurrence relation
  • · Replies 1 ·
Replies
1
Views
2K
How to Derive a Recurrence Relation for a Combined Geometric Sequence?
  • · Replies 1 ·
Replies
1
Views
2K
Solving Recurrence Relations in Matlab: A Homework Challenge
  • · Replies 9 ·
Replies
9
Views
5K
Undergrad The general notion of a recurrence relation
  • · Replies 18 ·
Replies
18
Views
3K