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>

Solve

Solution Stats

645 Solutions
119 Solvers

Last Solution submitted on Oct 14, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 3182251

1 Comment

1 Comment

Akrem Hadji on 12 Oct 2020 at 21:51

Nice problem :)

Problem Recent Solvers119

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 Solvers119

Suggested Problems

More from this Author41

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 Solvers119

Suggested Problems

More from this Author41

Problem Tags

Community Treasure Hunt

Players