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

1359 Solutions
254 Solvers

Last Solution submitted on Mar 17, 2023

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 Solvers254

Problem Tags

Community Treasure Hunt

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

Start Hunting!