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

539 Solutions
125 Solvers

Last Solution submitted on Sep 16, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers125

Problem Tags

fibonacci recurrence sequences

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers125

Suggested Problems

More from this Author41

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers125

Suggested Problems

More from this Author41

Problem Tags

Players