Problem 8057. (Linear) Recurrence Equations - Generalised Fibonacci-like sequences

Created by Jan Orwat

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is inspired by problems</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://uk.mathworks.com/matlabcentral/cody/problems/2187-generalized-fibonacci\"><w:r><w:t>2187</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://uk.mathworks.com/matlabcentral/cody/problems/3092-return-fibonacci-sequence-do-not-use-loop-and-condition\"><w:r><w:t>3092</w:t></w:r></w:hyperlink><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://uk.mathworks.com/matlabcentral/cody/?term=tag%3A%22fibonacci%22\"><w:r><w:t>other problems</w:t></w:r></w:hyperlink><w:r><w:t> based on Fibonacci sequence.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>I haven't seen here many problems based on other recursive sequences such as</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://oeis.org/A000032\"><w:r><w:t>Lucas numbers</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://oeis.org/A000129\"><w:r><w:t>Pell numbers</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://oeis.org/A000931\"><w:r><w:t>Padovan sequence</w:t></w:r></w:hyperlink><w:r><w:t> or</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://oeis.org/A000073\"><w:r><w:t>Tribonacci numbers</w:t></w:r></w:hyperlink><w:r><w:t> so this is a problem about them all.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your function input will be</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Init</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Rules</w:t></w:r><w:r><w:t>.</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Init</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Rules</w:t></w:r><w:r><w:t> represent initial values of sequence and a kernel which denotes recurrence relation:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ Init : [ A1 A2 ... Ak]\n Rules : [ Ck ... C2 C1]\n\n function: f(n) = (Ck) * f(n-k) + ... + (C2) * f(n-2) + (C1) * f(n-1)\n and f(1) = A1, f(2) = A2, ..., f(k) = Ak,]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>Init</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>Rules</w:t></w:r><w:r><w:t> have the same length,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> may be a single number or a vector. Your function should return values of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>f(N)</w:t></w:r><w:r><w:t>. Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ % Fibonacci sequence: f(1)=f(2)=1, f(n)=f(n-2)+f(n-1)\n >> Init = [1 1];\n >> Rules = [1 1];\n >> N = 1:10;\n >> fibonacci = recurrence_seq(N,Init,Rules),\n fibonacci = \n 1 1 2 3 5 8 13 21 34 55]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Other info:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Different approaches may lead to solutions which won't be able to compute</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>f(n)</w:t></w:r><w:r><w:t> for</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> being equal 0 or negative integer. If your solution doesn't return correct answer for those numbers it will still pass if it returns NaNs for</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>n&lt;1</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Please, try to avoid unnecessary things like strings,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>ans</w:t></w:r><w:r><w:t>, etc.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This problem is inspired by problems <a href = "http://uk.mathworks.com/matlabcentral/cody/problems/2187-generalized-fibonacci">2187</a>, <a href = "http://uk.mathworks.com/matlabcentral/cody/problems/3092-return-fibonacci-sequence-do-not-use-loop-and-condition">3092</a> and <a href = "http://uk.mathworks.com/matlabcentral/cody/?term=tag%3A%22fibonacci%22">other problems</a> based on Fibonacci sequence.I haven't seen here many problems based on other recursive sequences such as <a href = "http://oeis.org/A000032">Lucas numbers</a>, <a href = "http://oeis.org/A000129">Pell numbers</a>, <a href = "http://oeis.org/A000931">Padovan sequence</a> or <a href = "http://oeis.org/A000073">Tribonacci numbers</a> so this is a problem about them all.Your function input will be N, Init and Rules. Init and Rules represent initial values of sequence and a kernel which denotes recurrence relation:<pre> Init : [ A1 A2 ... Ak]
 Rules : [ Ck ... C2 C1]</pre><pre> function: f(n) = (Ck) * f(n-k) + ... + (C2) * f(n-2) + (C1) * f(n-1)
 and f(1) = A1, f(2) = A2, ..., f(k) = Ak,</pre>Init and Rules have the same length, N may be a single number or a vector. Your function should return values of f(N). Example:<pre> % Fibonacci sequence: f(1)=f(2)=1, f(n)=f(n-2)+f(n-1)
 &gt;&gt; Init = [1 1];
 &gt;&gt; Rules = [1 1];
 &gt;&gt; N = 1:10;
 &gt;&gt; fibonacci = recurrence_seq(N,Init,Rules),
 fibonacci = 
 1 1 2 3 5 8 13 21 34 55</pre>Other info:<ul><li>Different approaches may lead to solutions which won't be able to compute f(n) for n being equal 0 or negative integer. If your solution doesn't return correct answer for those numbers it will still pass if it returns NaNs for n&lt;1.</li><li>Please, try to avoid unnecessary things like strings, ans, etc.</li></ul>

This problem is inspired by problems <http://uk.mathworks.com/matlabcentral/cody/problems/2187-generalized-fibonacci 2187>, <http://uk.mathworks.com/matlabcentral/cody/problems/3092-return-fibonacci-sequence-do-not-use-loop-and-condition 3092> and <http://uk.mathworks.com/matlabcentral/cody/?term=tag%3A%22fibonacci%22 other problems> based on Fibonacci sequence.

I haven't seen here many problems based on other recursive sequences such as <http://oeis.org/A000032 Lucas numbers>, <http://oeis.org/A000129 Pell numbers>, <http://oeis.org/A000931 Padovan sequence> or <http://oeis.org/A000073 Tribonacci numbers> so this is a problem about them all.

Your function input will be _N_, _Init_ and _Rules_. _Init_ and _Rules_ represent initial values of sequence and a kernel which denotes recurrence relation:

Init  : [ A1 A2 ... Ak]
    Rules : [ Ck ... C2 C1]
  
    function: f(n) = (Ck) * f(n-k) + ... + (C2) * f(n-2) + (C1) * f(n-1)
              and f(1) = A1, f(2) = A2, ..., f(k) = Ak,

_Init_ and _Rules_ have the same length, _N_ may be a single number or a vector. Your function should return values of _f(N)_. Example:

% Fibonacci sequence:      f(1)=f(2)=1, f(n)=f(n-2)+f(n-1)
    >> Init = [1 1];
    >> Rules = [1 1];
    >> N = 1:10;
    >> fibonacci = recurrence_seq(N,Init,Rules),
    fibonacci = 
        1   1   2   3   5   8  13  21  34  55

Other info:

* Different approaches may lead to solutions which won't be able to compute _f(n)_ for _n_ being equal 0 or negative integer. If your solution doesn't return correct answer for those numbers it will still pass if it returns NaNs for _n<1_.
* Please, try to avoid unnecessary things like strings, _ans_, etc.

Solve

Solution Stats

1305 Solutions
245 Solvers

Last Solution submitted on Jun 20, 2022

Last 200 Solutions

Problem Comments

Solution Comments

Solution 7446195

1 Comment

1 Comment

Jayesh Kethwas on 28 Jan 2022

Really interesting problem

Solution 3182251

1 Comment

1 Comment

Akrem Hadji on 12 Oct 2020

Nice problem :)

Problem Recent Solvers245

Problem Tags

fibonacci recurrence sequences

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 8057. (Linear) Recurrence Equations - Generalised Fibonacci-like sequences

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers245

Suggested Problems

More from this Author40

Problem Tags

Community Treasure Hunt

Problem 8057. (Linear) Recurrence Equations - Generalised Fibonacci-like sequences

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers245

Suggested Problems

More from this Author40

Problem Tags

Community Treasure Hunt

Players