Find a recurrence relation.

In summary, the problem is to find a recurrence relation for the number of strictly increasing sequences of positive integers that start with 1 and end with n, where n is a positive integer. The solution involves considering the number of new sequences that are possible when n is increased by 1 and finding a mapping between these new sequences and the old ones. The recurrence relation is An = An-1 + An-2 + An-2 + An-3 + ... + An-k+ 1, where k is the number of steps and each step allows for a new recurrence. However, the exact computation of the number of new possible combinations is still unclear.
  • #1
AUCTA
10
0

Homework Statement


Find a recurrence relation for the number of stricly increasing sequences of positive integers that have
1 as their first term and n as their last term, where n is a positive integer. that is, sequences a1, a2, ..., ak, where a1 = 1, ak = n, and aj < aj+1 for j = 1, 2, ...k - 1


Homework Equations



Just recurrences

The Attempt at a Solution



An = An-1 + An-2 + An-2 + An-3 + ... + An-k+ 1 since you j can equal 1, 2, 3, ... k - 1 and every step
allows for a recurrence for that given number of steps. I just do not think the solution can be made like that. I thought about something like writing every large jump in terms of single jumps but I am not sure.

Thanks in advance for your help
 
Physics news on Phys.org
  • #2
If n is increased by 1, what sequences are possible that were not possible before? Can you think of a mapping between these and those that were already possible?
What sequences, if any, are no longer possible?
 
  • #3
Any sequence including n + 1 is a new sequence.

For the mapping we can think about it like this :
Total = New + Old
Old = An-1 where n is effectively n + 1

I am not exactly sure on how to compute the number of new possible combinations
 
  • #4
AUCTA said:
Any sequence including n + 1 is a new sequence.

For the mapping we can think about it like this :
No, that's not what I meant by a mapping. I mean a natural way of matching up new sequences with old ones.
 

1. What is a recurrence relation?

A recurrence relation is a mathematical equation or formula that defines a sequence recursively. It is a way of expressing a sequence by relating each term to one or more of the previous terms.

2. How do you find a recurrence relation?

To find a recurrence relation, you need to observe the pattern in the given sequence. You can then identify the relationship between the current term and the previous terms. This relationship can be expressed as an equation or formula, which becomes the recurrence relation.

3. Why is finding a recurrence relation important?

Finding a recurrence relation is important because it allows us to predict the terms in a sequence without having to explicitly list them. This can be useful in various fields, such as computer science, where it can help in designing algorithms and analyzing their efficiency.

4. What are some common methods for finding a recurrence relation?

Some common methods for finding a recurrence relation include using algebraic manipulation, using examples and patterns, and using generating functions. Other techniques, such as the Master Theorem and substitution method, can also be used depending on the complexity of the sequence.

5. Can a recurrence relation be solved to find a closed-form solution?

In some cases, a recurrence relation can be solved to find a closed-form solution, which is an explicit formula for calculating any term in the sequence without having to use the previous terms. However, not all recurrence relations have closed-form solutions, and in those cases, we can use approximation methods to estimate the terms in the sequence.

Similar threads

  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
937
  • Calculus and Beyond Homework Help
Replies
3
Views
931
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
429
  • Calculus and Beyond Homework Help
Replies
8
Views
925
  • Calculus and Beyond Homework Help
Replies
2
Views
887
  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
Back
Top