Linear recurrence with constant coefficients

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Linear recurrence with constant coefficients - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"6508258a-cc11-44dd-b5fc-73760c3e594c","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Linear_recurrence_with_constant_coefficients","wgTitle":"Linear recurrence with constant coefficients","wgCurRevisionId":1252039305,"wgRevisionId":1252039305,"wgArticleId":50700194,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Combinatorics","Dynamical systems","Linear algebra","Recurrence relations"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Linear_recurrence_with_constant_coefficients","wgRelevantArticleId":50700194,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q364089","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth", "ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Linear recurrence with constant coefficients - Wikipedia"> <meta property="og:type" content="website"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Linear_recurrence_with_constant_coefficients rootpage-Linear_recurrence_with_constant_coefficients skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Linear+recurrence+with+constant+coefficients" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Linear+recurrence+with+constant+coefficients" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Linear+recurrence+with+constant+coefficients" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Linear+recurrence+with+constant+coefficients" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definitions" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definitions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definitions</span> </div> </a> <ul id="toc-Definitions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Conversion_to_homogeneous_form" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Conversion_to_homogeneous_form"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Conversion to homogeneous form</span> </div> </a> <ul id="toc-Conversion_to_homogeneous_form-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Solution_example_for_small_orders" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Solution_example_for_small_orders"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Solution example for small orders</span> </div> </a> <button aria-controls="toc-Solution_example_for_small_orders-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Solution example for small orders subsection</span> </button> <ul id="toc-Solution_example_for_small_orders-sublist" class="vector-toc-list"> <li id="toc-Order_1" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Order_1"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Order 1</span> </div> </a> <ul id="toc-Order_1-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Order_2" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Order_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Order 2</span> </div> </a> <ul id="toc-Order_2-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-General_solution" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#General_solution"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>General solution</span> </div> </a> <button aria-controls="toc-General_solution-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle General solution subsection</span> </button> <ul id="toc-General_solution-sublist" class="vector-toc-list"> <li id="toc-Characteristic_polynomial_and_roots" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Characteristic_polynomial_and_roots"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Characteristic polynomial and roots</span> </div> </a> <ul id="toc-Characteristic_polynomial_and_roots-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Solution_with_distinct_characteristic_roots" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Solution_with_distinct_characteristic_roots"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Solution with distinct characteristic roots</span> </div> </a> <ul id="toc-Solution_with_distinct_characteristic_roots-sublist" class="vector-toc-list"> <li id="toc-Converting_complex_solution_to_trigonometric_form" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Converting_complex_solution_to_trigonometric_form"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2.1</span> <span>Converting complex solution to trigonometric form</span> </div> </a> <ul id="toc-Converting_complex_solution_to_trigonometric_form-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Cyclicity" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Cyclicity"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2.2</span> <span>Cyclicity</span> </div> </a> <ul id="toc-Cyclicity-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Solution_with_duplicate_characteristic_roots" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Solution_with_duplicate_characteristic_roots"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Solution with duplicate characteristic roots</span> </div> </a> <ul id="toc-Solution_with_duplicate_characteristic_roots-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Solution_by_conversion_to_matrix_form" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Solution_by_conversion_to_matrix_form"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Solution by conversion to matrix form</span> </div> </a> <ul id="toc-Solution_by_conversion_to_matrix_form-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Solution_using_generating_functions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Solution_using_generating_functions"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5</span> <span>Solution using generating functions</span> </div> </a> <ul id="toc-Solution_using_generating_functions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Relation_to_solution_to_differential_equations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Relation_to_solution_to_differential_equations"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6</span> <span>Relation to solution to differential equations</span> </div> </a> <ul id="toc-Relation_to_solution_to_differential_equations-sublist" class="vector-toc-list"> <li id="toc-Solving_with_z-transforms" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Solving_with_z-transforms"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6.1</span> <span>Solving with z-transforms</span> </div> </a> <ul id="toc-Solving_with_z-transforms-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Stability" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Stability"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Stability</span> </div> </a> <ul id="toc-Stability-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Linear recurrence with constant coefficients</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 4 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-4" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">4 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Recurr%C3%A8ncia_lineal_amb_coeficients_constants" title="Recurrència lineal amb coeficients constants – Catalan" lang="ca" hreflang="ca" data-title="Recurrència lineal amb coeficients constants" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Lineare_Differenzengleichung" title="Lineare Differenzengleichung – German" lang="de" hreflang="de" data-title="Lineare Differenzengleichung" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Ecuaci%C3%B3n_en_diferencia_lineal" title="Ecuación en diferencia lineal – Spanish" lang="es" hreflang="es" data-title="Ecuación en diferencia lineal" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E5%9B%9E%E5%B8%B0%E6%95%B0%E5%88%97" title="線型回帰数列 – Japanese" lang="ja" hreflang="ja" data-title="線型回帰数列" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q364089#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Linear_recurrence_with_constant_coefficients" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Linear_recurrence_with_constant_coefficients" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Linear_recurrence_with_constant_coefficients"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Linear_recurrence_with_constant_coefficients"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Linear_recurrence_with_constant_coefficients" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Linear_recurrence_with_constant_coefficients" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&oldid=1252039305" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Linear_recurrence_with_constant_coefficients&id=1252039305&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLinear_recurrence_with_constant_coefficients"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FLinear_recurrence_with_constant_coefficients"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Linear_recurrence_with_constant_coefficients&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q364089" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Relation in Algebra</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="/wiki/Constant-recursive_sequence" title="Constant-recursive sequence">Constant-recursive sequence</a></div> <p>In <a href="/wiki/Mathematics" title="Mathematics">mathematics</a> (including <a href="/wiki/Combinatorics" title="Combinatorics">combinatorics</a>, <a href="/wiki/Linear_algebra" title="Linear algebra">linear algebra</a>, and <a href="/wiki/Dynamical_systems" class="mw-redirect" title="Dynamical systems">dynamical systems</a>), a <b>linear recurrence with constant coefficients</b><sup id="cite_ref-Chiang_1-0" class="reference"><a href="#cite_note-Chiang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: ch. 17">: ch. 17 </span></sup><sup id="cite_ref-Baumol_2-0" class="reference"><a href="#cite_note-Baumol-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Location: ch. 10">: ch. 10 </span></sup> (also known as a <b>linear recurrence relation</b> or <b>linear difference equation</b>) sets equal to 0 a <a href="/wiki/Polynomial" title="Polynomial">polynomial</a> that is linear in the various iterates of a <a href="/wiki/Variable_(mathematics)" title="Variable (mathematics)">variable</a>—that is, in the values of the elements of a <a href="/wiki/Sequence" title="Sequence">sequence</a>. The polynomial's linearity means that each of its terms has <a href="/wiki/Degree_of_a_polynomial" title="Degree of a polynomial">degree</a> 0 or 1. A linear recurrence denotes the evolution of some variable over time, with the current <a href="/wiki/Discrete_time" class="mw-redirect" title="Discrete time">time period</a> or discrete moment in time denoted as <span class="texhtml mvar" style="font-style:italic;">t</span>, one period earlier denoted as <span class="texhtml"><i>t</i> − 1</span>, one period later as <span class="texhtml"><i>t</i> + 1</span>, etc. </p><p>The <i><a href="/wiki/Equation_solving" title="Equation solving">solution</a></i> of such an equation is a function of <span class="texhtml mvar" style="font-style:italic;">t</span>, and not of any iterate values, giving the value of the iterate at any time. To find the solution it is necessary to know the specific values (known as <i><a href="/wiki/Initial_condition" title="Initial condition">initial conditions</a></i>) of <span class="texhtml mvar" style="font-style:italic;">n</span> of the iterates, and normally these are the <span class="texhtml mvar" style="font-style:italic;">n</span> iterates that are oldest. The equation or its variable is said to be <i><a href="/wiki/Lyapunov_stability#Definition_for_discrete-time_systems" title="Lyapunov stability">stable</a></i> if from any set of initial conditions the variable's limit as time goes to infinity exists; this limit is called the <i><a href="/wiki/Steady_state" title="Steady state">steady state</a></i>. </p><p>Difference equations are used in a variety of contexts, such as in <a href="/wiki/Economics" title="Economics">economics</a> to model the evolution through time of variables such as <a href="/wiki/Gross_domestic_product" title="Gross domestic product">gross domestic product</a>, the <a href="/wiki/Inflation_rate" class="mw-redirect" title="Inflation rate">inflation rate</a>, the <a href="/wiki/Exchange_rate" title="Exchange rate">exchange rate</a>, etc. They are used in modeling such <a href="/wiki/Time_series" title="Time series">time series</a> because values of these variables are only measured at discrete intervals. In <a href="/wiki/Econometrics" title="Econometrics">econometric</a> applications, linear difference equations are modeled with <a href="/wiki/Stochastic_process" title="Stochastic process">stochastic terms</a> in the form of <a href="/wiki/Autoregressive_model" title="Autoregressive model">autoregressive (AR) models</a> and in models such as <a href="/wiki/Vector_autoregression" title="Vector autoregression">vector autoregression</a> (VAR) and <a href="/wiki/Autoregressive_moving_average" class="mw-redirect" title="Autoregressive moving average">autoregressive moving average</a> (ARMA) models that combine AR with other features. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=1" title="Edit section: Definitions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <b>linear recurrence with constant coefficients</b> is an equation of the following form, written in terms of <a href="/wiki/Parameter#Mathematical_functions" title="Parameter">parameters</a> <span class="texhtml"><i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>n</i></sub></span> and <span class="texhtml mvar" style="font-style:italic;">b</span>: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/341a2d12ce92e3fea7d84164718915a07861be18" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:30.98ex; height:2.509ex;" alt="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}"></span> </p><p>or equivalently as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t+n}=a_{1}y_{t+n-1}+\cdots +a_{n}y_{t}+b.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>+</mo> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>+</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t+n}=a_{1}y_{t+n-1}+\cdots +a_{n}y_{t}+b.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6833536df902cd1bac8b8844aa6a08f4dce5a56e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:33.245ex; height:2.509ex;" alt="{\displaystyle y_{t+n}=a_{1}y_{t+n-1}+\cdots +a_{n}y_{t}+b.}"></span> </p><p>The positive integer <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> is called the <b>order</b> of the recurrence and denotes the longest time lag between iterates. The equation is called <b>homogeneous</b> if <span class="texhtml"><i>b</i> = 0</span> and <b>nonhomogeneous</b> if <span class="texhtml"><i>b</i> ≠ 0</span>. </p><p>If the equation is homogeneous, the coefficients determine the <b><a href="/wiki/Characteristic_polynomial" title="Characteristic polynomial">characteristic polynomial</a></b> (also "auxiliary polynomial" or "companion polynomial") </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(\lambda )=\lambda ^{n}-a_{1}\lambda ^{n-1}-a_{2}\lambda ^{n-2}-\cdots -a_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo stretchy="false">(</mo> <mi>λ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p(\lambda )=\lambda ^{n}-a_{1}\lambda ^{n-1}-a_{2}\lambda ^{n-2}-\cdots -a_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11312ffd46ec2821062dbe38994a2a60593006d5" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:40.545ex; height:3.176ex;" alt="{\displaystyle p(\lambda )=\lambda ^{n}-a_{1}\lambda ^{n-1}-a_{2}\lambda ^{n-2}-\cdots -a_{n}}"></span> </p><p>whose roots play a crucial role in finding and understanding the sequences satisfying the recurrence. </p> <div class="mw-heading mw-heading2"><h2 id="Conversion_to_homogeneous_form">Conversion to homogeneous form</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=2" title="Edit section: Conversion to homogeneous form"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If <span class="texhtml"><i>b</i> ≠ 0</span>, the equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/146df31fc15b21d14f97d904d47812a365369ee1" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:30.334ex; height:2.509ex;" alt="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}"></span> </p><p>is said to be <i>nonhomogeneous</i>. To solve this equation it is convenient to convert it to homogeneous form, with no constant term. This is done by first finding the equation's <i>steady state value</i>—a value <span class="texhtml"><i>y</i>*</span> such that, if <span class="texhtml mvar" style="font-style:italic;">n</span> successive iterates all had this value, so would all future values. This value is found by setting all values of <span class="texhtml mvar" style="font-style:italic;">y</span> equal to <span class="texhtml"><i>y</i>*</span> in the difference equation, and solving, thus obtaining </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{n}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>b</mi> <mrow> <mn>1</mn> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{n}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3de09ab34c228541a7db9deec305e58bb501eeec" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:23.289ex; height:5.676ex;" alt="{\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{n}}}}"></span> </p><p>assuming the denominator is not 0. If it is zero, the steady state does not exist. </p><p>Given the steady state, the difference equation can be rewritten in terms of deviations of the iterates from the steady state, as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(y_{t}-y^{*}\right)=a_{1}\left(y_{t-1}-y^{*}\right)+\cdots +a_{n}\left(y_{t-n}-y^{*}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>(</mo> <mrow> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>−</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mrow> <mo>)</mo> </mrow> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>−</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left(y_{t}-y^{*}\right)=a_{1}\left(y_{t-1}-y^{*}\right)+\cdots +a_{n}\left(y_{t-n}-y^{*}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/325a3036a7c1bbf962b8b0b5d34bff7f451cc34d" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.863ex; height:2.843ex;" alt="{\displaystyle \left(y_{t}-y^{*}\right)=a_{1}\left(y_{t-1}-y^{*}\right)+\cdots +a_{n}\left(y_{t-n}-y^{*}\right)}"></span> </p><p>which has no constant term, and which can be written more succinctly as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/baccbe176606f98f5df7e6267145051181ffaf93" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.067ex; height:2.343ex;" alt="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"></span> </p><p>where <span class="texhtml mvar" style="font-style:italic;">x</span> equals <span class="texhtml"><i>y</i> − <i>y</i>*</span>. This is the homogeneous form. </p><p>If there is no steady state, the difference equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/146df31fc15b21d14f97d904d47812a365369ee1" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:30.334ex; height:2.509ex;" alt="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}"></span> </p><p>can be combined with its equivalent form </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t-1}=a_{1}y_{t-2}+\cdots +a_{n}y_{t-(n+1)}+b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t-1}=a_{1}y_{t-2}+\cdots +a_{n}y_{t-(n+1)}+b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d120d3ce559191d4098d34d6910824ad4cabfbd" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:35.814ex; height:3.009ex;" alt="{\displaystyle y_{t-1}=a_{1}y_{t-2}+\cdots +a_{n}y_{t-(n+1)}+b}"></span> </p><p>to obtain (by solving both for <span class="texhtml mvar" style="font-style:italic;">b</span>) </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16a6abcfbbf75850b52a51e1945038e25d6718b4" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:61.054ex; height:2.843ex;" alt="{\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}"></span> </p><p>in which like terms can be combined to give a homogeneous equation of one order higher than the original. </p> <div class="mw-heading mw-heading2"><h2 id="Solution_example_for_small_orders">Solution example for small orders</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=3" title="Edit section: Solution example for small orders"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The roots of the characteristic polynomial play a crucial role in finding and understanding the sequences satisfying the recurrence. If there are <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span> distinct roots <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1},r_{2},\ldots ,r_{d},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{1},r_{2},\ldots ,r_{d},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dc219f66dabe1252cea772495ab1b69c3ba9f8bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.205ex; height:2.009ex;" alt="{\displaystyle r_{1},r_{2},\ldots ,r_{d},}"></span> then each solution to the recurrence takes the form <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msubsup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msubsup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msub> <msubsup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9eb341219fb3d4096b13c6129260110c442b3814" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.074ex; height:2.843ex;" alt="{\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}"></span> where the coefficients <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f29138ed3ad54ffce527daccadc49c520459b0b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.011ex; height:2.509ex;" alt="{\displaystyle k_{i}}"></span> are determined in order to fit the initial conditions of the recurrence. When the same roots occur multiple times, the terms in this formula corresponding to the second and later occurrences of the same root are multiplied by increasing powers of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. For instance, if the characteristic polynomial can be factored as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x-r)^{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <mi>r</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x-r)^{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f796f6512a5b6e1424865145a118bdba61e74d65" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.082ex; height:3.176ex;" alt="{\displaystyle (x-r)^{3}}"></span>, with the same root <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"></span> occurring three times, then the solution would take the form <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mi>n</mi> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/711672b659b4ffa62f30f38721db728be6046834" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:29.316ex; height:3.009ex;" alt="{\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}"></span><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Order_1">Order 1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=4" title="Edit section: Order 1"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For order 1, the recurrence <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=ra_{n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>r</mi> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=ra_{n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/097fe61e61a6729bfe569fd473434a82411973cb" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.144ex; height:2.009ex;" alt="{\displaystyle a_{n}=ra_{n-1}}"></span> has the solution <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=r^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=r^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c13d05830a4e93cdb69633ebea35f0375bb2ff38" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.814ex; height:2.676ex;" alt="{\displaystyle a_{n}=r^{n}}"></span> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{0}=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3873789cb6451e25f63b4d11572ac5c69d7873b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.545ex; height:2.509ex;" alt="{\displaystyle a_{0}=1}"></span> and the most general solution is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=kr^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>k</mi> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=kr^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a364a14d1345bf63bc326c66dd9fe8ce45cb5b9c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.025ex; height:2.676ex;" alt="{\displaystyle a_{n}=kr^{n}}"></span> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}=k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{0}=k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/da2678f798ea0c17ef6178d4faa76ab19834cf55" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.594ex; height:2.509ex;" alt="{\displaystyle a_{0}=k}"></span>. The characteristic polynomial equated to zero (the <a href="/wiki/Characteristic_polynomial" title="Characteristic polynomial">characteristic equation</a>) is simply <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t-r=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>t</mi> <mo>−</mo> <mi>r</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t-r=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d325e8656f65bbd50bdc015aa1d3c86df34c0dd5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.99ex; height:2.343ex;" alt="{\displaystyle t-r=0}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Order_2">Order 2</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=5" title="Edit section: Order 2"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Solutions to such recurrence relations of higher order are found by systematic means, often using the fact that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=r^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=r^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c13d05830a4e93cdb69633ebea35f0375bb2ff38" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.814ex; height:2.676ex;" alt="{\displaystyle a_{n}=r^{n}}"></span> is a solution for the recurrence exactly when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>t</mi> <mo>=</mo> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t=r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/481c002fdf2c8f8027c5d10a7f4d06feec04694f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.987ex; height:2.009ex;" alt="{\displaystyle t=r}"></span> is a root of the characteristic polynomial. This can be approached directly or using <a href="/wiki/Generating_function" title="Generating function">generating functions</a> (<a href="/wiki/Formal_power_series" title="Formal power series">formal power series</a>) or matrices. </p><p>Consider, for example, a recurrence relation of the form <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>A</mi> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mi>B</mi> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2622faf3e79d4160575f91c6de20d9aa073ed6da" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.639ex; height:2.509ex;" alt="{\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}"></span> </p><p>When does it have a solution of the same general form as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=r^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=r^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c13d05830a4e93cdb69633ebea35f0375bb2ff38" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.814ex; height:2.676ex;" alt="{\displaystyle a_{n}=r^{n}}"></span>? Substituting this guess (<a href="/wiki/Ansatz" title="Ansatz">ansatz</a>) in the recurrence relation, we find that <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>=</mo> <mi>A</mi> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <mi>B</mi> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f0e2912ef9c5395a5ce53da70ebe928b803022ec" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.448ex; height:2.843ex;" alt="{\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}"></span> must be true for <b>all</b> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n>1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>></mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n>1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee74e1cc07e7041edf0fcbd4481f5cd32ad17b64" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n>1}"></span>. </p><p>Dividing through by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r^{n-2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r^{n-2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6d0c38b91e909038143667e6ff1dae6d978e3d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.368ex; height:2.676ex;" alt="{\displaystyle r^{n-2}}"></span>, we get that all these equations reduce to the same thing: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}r^{2}&=Ar+B,\\r^{2}-Ar-B&=0,\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>A</mi> <mi>r</mi> <mo>+</mo> <mi>B</mi> <mo>,</mo> </mtd> </mtr> <mtr> <mtd> <msup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mi>A</mi> <mi>r</mi> <mo>−</mo> <mi>B</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mn>0</mn> <mo>,</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}r^{2}&=Ar+B,\\r^{2}-Ar-B&=0,\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25d1d34515abf2700105d766d71199e16e7100a5" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.232ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}r^{2}&=Ar+B,\\r^{2}-Ar-B&=0,\end{aligned}}}"></span> </p><p>which is the characteristic equation of the recurrence relation. Solve for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"></span> to obtain the two roots <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/571a423bece8f29bcd1b48572f18dd4f6213dce2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{1}}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b668a1bd1e8ab9452ca975b7497546e7c1ba187" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{2}}"></span>: these roots are known as the <a href="/wiki/Characteristic_root" class="mw-redirect" title="Characteristic root">characteristic roots</a> or <b>eigenvalues</b> of the characteristic equation. Different solutions are obtained depending on the nature of the roots: If these roots are distinct, we have the general solution </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>C</mi> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>+</mo> <mi>D</mi> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7f1d0fe11906ce095f1e2e0b24d1be59ce5038f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.225ex; height:2.843ex;" alt="{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}"></span> </p><p>while if they are identical (when <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{2}+4B=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>4</mn> <mi>B</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A^{2}+4B=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/66c4e6c7d83b3ba83a1318e8d973c92fcb566b2b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.825ex; height:2.843ex;" alt="{\displaystyle A^{2}+4B=0}"></span>), we have </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>C</mi> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>+</mo> <mi>D</mi> <mi>n</mi> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a00e073789c4d13ac252abba43bc112e18e74a69" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.62ex; height:2.676ex;" alt="{\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}"></span> </p><p>This is the most general solution; the two constants <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}"></span> can be chosen based on two given initial conditions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/693ad9f934775838bd72406b41ada4a59785d7ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{0}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bbf42ecda092975c9c69dae84e16182ba5fe2e07" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}"></span> to produce a specific solution. </p><p>In the case of complex eigenvalues (which also gives rise to complex values for the solution parameters <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>D</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle D}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}"></span>), the use of complex numbers can be eliminated by rewriting the solution in trigonometric form. In this case we can write the eigenvalues as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mi>α</mi> <mo>±</mo> <mi>β</mi> <mi>i</mi> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19fbad5d83ca7d63fbbd661e0f8e413ecd9fcea5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.061ex; height:2.509ex;" alt="{\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.}"></span> Then it can be shown that </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mi>C</mi> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> <mo>+</mo> <mi>D</mi> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7f1d0fe11906ce095f1e2e0b24d1be59ce5038f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.225ex; height:2.843ex;" alt="{\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}"></span> </p><p>can be rewritten as<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Pages: 576–585">: 576–585 </span></sup> </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mn>2</mn> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mrow> <mo>(</mo> <mrow> <mi>E</mi> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>n</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>F</mi> <mi>sin</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mn>2</mn> <mi>G</mi> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>n</mi> <mo>−</mo> <mi>δ</mi> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/64f620c1b2bd9bf35fb00e962e62cb1c58e4b2db" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.443ex; height:2.843ex;" alt="{\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}"></span> </p><p>where </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="left center left" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mi>M</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>β</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </msqrt> </mrow> </mtd> <mtd> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>α</mi> <mi>M</mi> </mfrac> </mstyle> </mrow> </mtd> <mtd> <mi>sin</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>β</mi> <mi>M</mi> </mfrac> </mstyle> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>C</mi> <mo>,</mo> <mi>D</mi> <mo>=</mo> <mi>E</mi> <mo>∓</mo> <mi>F</mi> <mi>i</mi> </mtd> <mtd /> <mtd /> </mtr> <mtr> <mtd> <mi>G</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>F</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </msqrt> </mrow> </mtd> <mtd> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>δ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>E</mi> <mi>G</mi> </mfrac> </mstyle> </mrow> </mtd> <mtd> <mi>sin</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>δ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mi>F</mi> <mi>G</mi> </mfrac> </mstyle> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a4fb184dfb123c453c23b995bc6a0292665e99aa" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.967ex; margin-bottom: -0.204ex; width:44.292ex; height:11.509ex;" alt="{\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}"></span> </p><p>Here <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> (or equivalently, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span>) are real constants which depend on the initial conditions. Using <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mn>2</mn> <mi>α</mi> <mo>=</mo> <mi>A</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/77826d78184c86f7aa91cfb36ea91cf5de8df508" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.896ex; height:2.509ex;" alt="{\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⋅</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msup> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>β</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>=</mo> <mo>−</mo> <mi>B</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6dc93e9a9c553738f84e560ce20d902fc4209026" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.687ex; height:3.009ex;" alt="{\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}"></span> </p><p>one may simplify the solution given above as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mi>B</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> </msup> <mrow> <mo>(</mo> <mrow> <mi>E</mi> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>n</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mi>F</mi> <mi>sin</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>)</mo> </mrow> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/afde21a075cb30be1a8029d98142fc3e186ebf45" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:37.714ex; height:3.676ex;" alt="{\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}"></span> </p><p>where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bbf42ecda092975c9c69dae84e16182ba5fe2e07" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/270580da7333505d9b73697417d0543c43c98b9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{2}}"></span> are the initial conditions and </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <mi>E</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mo>−</mo> <mi>A</mi> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mrow> <mi>B</mi> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>F</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mo>−</mo> <mi>i</mi> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>−</mo> <mi>A</mi> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <mn>2</mn> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mi>B</mi> </mrow> <mrow> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>4</mn> <mi>B</mi> </msqrt> </mrow> </mrow> </mfrac> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>θ</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>arccos</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>A</mi> <mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mo>−</mo> <mi>B</mi> </msqrt> </mrow> </mrow> </mfrac> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b7168aacf6476d50de56011f02c5027b38edb96a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.005ex; width:29.072ex; height:19.176ex;" alt="{\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}"></span> </p><p>In this way there is no need to solve for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/571a423bece8f29bcd1b48572f18dd4f6213dce2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b668a1bd1e8ab9452ca975b7497546e7c1ba187" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.409ex; height:2.509ex;" alt="{\displaystyle \lambda _{2}}"></span>. </p><p>In all cases—real distinct eigenvalues, real duplicated eigenvalues, and complex conjugate eigenvalues—the equation is <a href="/wiki/Stability_theory" title="Stability theory">stable</a> (that is, the variable <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"></span> converges to a fixed value [specifically, zero]) if and only if <i>both</i> eigenvalues are smaller than one in <a href="/wiki/Absolute_value" title="Absolute value">absolute value</a>. In this second-order case, this condition on the eigenvalues can be shown<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> to be equivalent to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |A|<1-B<2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo><</mo> <mn>1</mn> <mo>−</mo> <mi>B</mi> <mo><</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |A|<1-B<2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fce0a381ac5f68a28fc7c08574cfc30234aeee78" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.163ex; height:2.843ex;" alt="{\displaystyle |A|<1-B<2}"></span>, which is equivalent to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |B|<1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>B</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo><</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |B|<1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ff20b72e712e618b261f6863d37dc8b97fe5eda" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.319ex; height:2.843ex;" alt="{\displaystyle |B|<1}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |A|<1-B}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>A</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo><</mo> <mn>1</mn> <mo>−</mo> <mi>B</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |A|<1-B}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ddc9e141c31d5ef79302fa52c8150652e5cc6c80" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.902ex; height:2.843ex;" alt="{\displaystyle |A|<1-B}"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="General_solution">General solution</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=6" title="Edit section: General solution"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Recurrence_equation#Solving_homogeneous_linear_recurrence_relations_with_constant_coefficients" class="mw-redirect" title="Recurrence equation">Recurrence equation § Solving homogeneous linear recurrence relations with constant coefficients</a></div> <div class="mw-heading mw-heading3"><h3 id="Characteristic_polynomial_and_roots">Characteristic polynomial and roots</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=7" title="Edit section: Characteristic polynomial and roots"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Solving the homogeneous equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/baccbe176606f98f5df7e6267145051181ffaf93" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.067ex; height:2.343ex;" alt="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"></span> </p><p>involves first solving its characteristic polynomial </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mi>λ</mi> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9def9d20e70d97a5d5661ed41e762663fc1f97eb" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:42.026ex; height:3.009ex;" alt="{\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}}"></span> </p><p>for its characteristic roots <span class="texhtml"><i>λ</i><sub>1</sub>, ..., <i>λ</i><sub><i>n</i></sub></span>. These roots can be solved for <a href="/wiki/Algebraic_expression" title="Algebraic expression">algebraically</a> if <span class="texhtml"><i>n</i> ≤ 4</span>, but <a href="/wiki/Abel%E2%80%93Ruffini_theorem" title="Abel–Ruffini theorem">not necessarily otherwise</a>. If the solution is to be used numerically, all the roots of this characteristic equation can be found by <a href="/wiki/Numerical_methods" class="mw-redirect" title="Numerical methods">numerical methods</a>. However, for use in a theoretical context it may be that the only information required about the roots is whether any of them are greater than or equal to 1 in <a href="/wiki/Absolute_value" title="Absolute value">absolute value</a>. </p><p>It may be that all the roots are <a href="/wiki/Real_number" title="Real number">real</a> or instead there may be some that are <a href="/wiki/Complex_number" title="Complex number">complex numbers</a>. In the latter case, all the complex roots come in <a href="/wiki/Complex_conjugate" title="Complex conjugate">complex conjugate</a> pairs. </p> <div class="mw-heading mw-heading3"><h3 id="Solution_with_distinct_characteristic_roots">Solution with distinct characteristic roots</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=8" title="Edit section: Solution with distinct characteristic roots"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If all the characteristic roots are distinct, the solution of the homogeneous linear recurrence </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/baccbe176606f98f5df7e6267145051181ffaf93" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.067ex; height:2.343ex;" alt="{\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}"></span> </p><p>can be written in terms of the characteristic roots as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63283041032b232d3db76a269a1654cee36625b5" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.928ex; height:3.176ex;" alt="{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}}"></span> </p><p>where the coefficients <span class="texhtml"><i>c</i><sub><i>i</i></sub></span> can be found by invoking the initial conditions. Specifically, for each time period for which an iterate value is known, this value and its corresponding value of <span class="texhtml mvar" style="font-style:italic;">t</span> can be substituted into the solution equation to obtain a linear equation in the <span class="texhtml mvar" style="font-style:italic;">n</span> as-yet-unknown parameters; <span class="texhtml mvar" style="font-style:italic;">n</span> such equations, one for each initial condition, can be <a href="/wiki/System_of_linear_equations" title="System of linear equations">solved simultaneously</a> for the <span class="texhtml mvar" style="font-style:italic;">n</span> parameter values. If all characteristic roots are real, then all the coefficient values <span class="texhtml"><i>c</i><sub><i>i</i></sub></span> will also be real; but with non-real complex roots, in general some of these coefficients will also be non-real. </p> <div class="mw-heading mw-heading4"><h4 id="Converting_complex_solution_to_trigonometric_form">Converting complex solution to trigonometric form</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=9" title="Edit section: Converting complex solution to trigonometric form"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>If there are complex roots, they come in conjugate pairs and so do the complex terms in the solution equation. If two of these complex terms are <span class="texhtml"><i>c</i><sub><i>j</i></sub><i>λ</i><span class="nowrap"><span style="display:inline-block;margin-bottom:-0.3em;vertical-align:-0.4em;line-height:1.2em;font-size:80%;text-align:left"><sup style="font-size:inherit;line-height:inherit;vertical-align:baseline"><i>t</i></sup><br /><sub style="font-size:inherit;line-height:inherit;vertical-align:baseline"><i>j</i></sub></span></span></span> and <span class="texhtml"><i>c</i><sub><i>j</i>+1</sub><i>λ</i><span class="nowrap"><span style="display:inline-block;margin-bottom:-0.3em;vertical-align:-0.4em;line-height:1.2em;font-size:80%;text-align:left"><sup style="font-size:inherit;line-height:inherit;vertical-align:baseline"><i>t</i></sup><br /><sub style="font-size:inherit;line-height:inherit;vertical-align:baseline"><i>j</i>+1</sub></span></span></span>, the roots <span class="texhtml"><i>λ</i><sub><i>j</i></sub></span> can be written as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{j},\lambda _{j+1}=\alpha \pm \beta i=M\left({\frac {\alpha }{M}}\pm {\frac {\beta }{M}}i\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>α</mi> <mo>±</mo> <mi>β</mi> <mi>i</mi> <mo>=</mo> <mi>M</mi> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>α</mi> <mi>M</mi> </mfrac> </mrow> <mo>±</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>β</mi> <mi>M</mi> </mfrac> </mrow> <mi>i</mi> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{j},\lambda _{j+1}=\alpha \pm \beta i=M\left({\frac {\alpha }{M}}\pm {\frac {\beta }{M}}i\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/be21b89ebae6ac87d79df78082457cccee7c5fd0" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:36.774ex; height:6.176ex;" alt="{\displaystyle \lambda _{j},\lambda _{j+1}=\alpha \pm \beta i=M\left({\frac {\alpha }{M}}\pm {\frac {\beta }{M}}i\right)}"></span> </p><p>where <span class="texhtml mvar" style="font-style:italic;">i</span> is the <a href="/wiki/Imaginary_unit" title="Imaginary unit">imaginary unit</a> and <span class="texhtml mvar" style="font-style:italic;">M</span> is the <a href="/wiki/Absolute_value" title="Absolute value">modulus</a> of the roots: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M={\sqrt {\alpha ^{2}+\beta ^{2}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>β</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </msqrt> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M={\sqrt {\alpha ^{2}+\beta ^{2}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d0cd8a91326a36493c97bc9f642dab9adf65f17c" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:16.285ex; height:4.843ex;" alt="{\displaystyle M={\sqrt {\alpha ^{2}+\beta ^{2}}}.}"></span> </p><p>Then the two complex terms in the solution equation can be written as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}c_{j}\lambda _{j}^{t}+c_{j+1}\lambda _{j+1}^{t}&=M^{t}\left(c_{j}\left({\frac {\alpha }{M}}+{\frac {\beta }{M}}i\right)^{t}+c_{j+1}\left({\frac {\alpha }{M}}-{\frac {\beta }{M}}i\right)^{t}\right)\\[6pt]&=M^{t}\left(c_{j}\left(\cos \theta +i\sin \theta \right)^{t}+c_{j+1}\left(\cos \theta -i\sin \theta \right)^{t}\right)\\[6pt]&=M^{t}{\bigl (}c_{j}\left(\cos \theta t+i\sin \theta t\right)+c_{j+1}\left(\cos \theta t-i\sin \theta t\right){\bigr )}\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="0.9em 0.9em 0.3em" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mrow> <mo>(</mo> <mrow> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <msup> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>α</mi> <mi>M</mi> </mfrac> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>β</mi> <mi>M</mi> </mfrac> </mrow> <mi>i</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msup> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>α</mi> <mi>M</mi> </mfrac> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>β</mi> <mi>M</mi> </mfrac> </mrow> <mi>i</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mrow> <mo>(</mo> <mrow> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <msup> <mrow> <mo>(</mo> <mrow> <mi>cos</mi> <mo>⁡</mo> <mi>θ</mi> <mo>+</mo> <mi>i</mi> <mi>sin</mi> <mo>⁡</mo> <mi>θ</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msup> <mrow> <mo>(</mo> <mrow> <mi>cos</mi> <mo>⁡</mo> <mi>θ</mi> <mo>−</mo> <mi>i</mi> <mi>sin</mi> <mo>⁡</mo> <mi>θ</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> </mrow> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <mi>cos</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> <mo>+</mo> <mi>i</mi> <mi>sin</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> </mrow> <mo>)</mo> </mrow> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <mi>cos</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> <mo>−</mo> <mi>i</mi> <mi>sin</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}c_{j}\lambda _{j}^{t}+c_{j+1}\lambda _{j+1}^{t}&=M^{t}\left(c_{j}\left({\frac {\alpha }{M}}+{\frac {\beta }{M}}i\right)^{t}+c_{j+1}\left({\frac {\alpha }{M}}-{\frac {\beta }{M}}i\right)^{t}\right)\\[6pt]&=M^{t}\left(c_{j}\left(\cos \theta +i\sin \theta \right)^{t}+c_{j+1}\left(\cos \theta -i\sin \theta \right)^{t}\right)\\[6pt]&=M^{t}{\bigl (}c_{j}\left(\cos \theta t+i\sin \theta t\right)+c_{j+1}\left(\cos \theta t-i\sin \theta t\right){\bigr )}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63653e50e3d50b416682c2dcd65d0437bea311e5" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.171ex; width:67.525ex; height:17.509ex;" alt="{\displaystyle {\begin{aligned}c_{j}\lambda _{j}^{t}+c_{j+1}\lambda _{j+1}^{t}&=M^{t}\left(c_{j}\left({\frac {\alpha }{M}}+{\frac {\beta }{M}}i\right)^{t}+c_{j+1}\left({\frac {\alpha }{M}}-{\frac {\beta }{M}}i\right)^{t}\right)\\[6pt]&=M^{t}\left(c_{j}\left(\cos \theta +i\sin \theta \right)^{t}+c_{j+1}\left(\cos \theta -i\sin \theta \right)^{t}\right)\\[6pt]&=M^{t}{\bigl (}c_{j}\left(\cos \theta t+i\sin \theta t\right)+c_{j+1}\left(\cos \theta t-i\sin \theta t\right){\bigr )}\end{aligned}}}"></span> </p><p>where <span class="texhtml mvar" style="font-style:italic;">θ</span> is the angle whose cosine is <span class="texhtml"><style data-mw-deduplicate="TemplateStyles:r1214402035">.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}</style><span class="sfrac">⁠<span class="tion"><span class="num"><i>α</i></span><span class="sr-only">/</span><span class="den"><i>M</i></span></span>⁠</span></span> and whose sine is <span class="texhtml"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num"><i>β</i></span><span class="sr-only">/</span><span class="den"><i>M</i></span></span>⁠</span></span>; the last equality here made use of <a href="/wiki/De_Moivre%27s_formula" title="De Moivre's formula">de Moivre's formula</a>. </p><p>Now the process of finding the coefficients <span class="texhtml"><i>c</i><sub><i>j</i></sub></span> and <span class="texhtml"><i>c</i><sub><i>j</i>+1</sub></span> guarantees that they are also complex conjugates, which can be written as <span class="texhtml"><i>γ</i> ± <i>δi</i></span>. Using this in the last equation gives this expression for the two complex terms in the solution equation: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2M^{t}\left(\gamma \cos \theta t-\delta \sin \theta t\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mrow> <mo>(</mo> <mrow> <mi>γ</mi> <mi>cos</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> <mo>−</mo> <mi>δ</mi> <mi>sin</mi> <mo>⁡</mo> <mi>θ</mi> <mi>t</mi> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2M^{t}\left(\gamma \cos \theta t-\delta \sin \theta t\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c322b11d18b0eb9a2553873d6fb5746f06169069" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.21ex; height:3.009ex;" alt="{\displaystyle 2M^{t}\left(\gamma \cos \theta t-\delta \sin \theta t\right)}"></span> </p><p>which can also be written as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2{\sqrt {\gamma ^{2}+\delta ^{2}}}M^{t}\cos(\theta t+\psi )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <msup> <mi>γ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>δ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </msqrt> </mrow> <msup> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mi>cos</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>θ</mi> <mi>t</mi> <mo>+</mo> <mi>ψ</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2{\sqrt {\gamma ^{2}+\delta ^{2}}}M^{t}\cos(\theta t+\psi )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c9fcedce4b3d6cdecb8378ac9b862833fc4e49d8" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.671ex; width:25.684ex; height:4.843ex;" alt="{\displaystyle 2{\sqrt {\gamma ^{2}+\delta ^{2}}}M^{t}\cos(\theta t+\psi )}"></span> </p><p>where <span class="texhtml mvar" style="font-style:italic;">ψ</span> is the angle whose cosine is <span class="texhtml"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num"><i>γ</i></span><span class="sr-only">/</span><span class="den"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>γ</i><sup>2</sup> + <i>δ</i><sup>2</sup></span></span></span></span>⁠</span></span> and whose sine is <span class="texhtml"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035"><span class="sfrac">⁠<span class="tion"><span class="num"><i>δ</i></span><span class="sr-only">/</span><span class="den"><span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;"><i>γ</i><sup>2</sup> + <i>δ</i><sup>2</sup></span></span></span></span>⁠</span></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Cyclicity">Cyclicity</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=10" title="Edit section: Cyclicity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Depending on the initial conditions, even with all roots real the iterates can experience a transitory tendency to go above and below the steady state value. But true cyclicity involves a permanent tendency to fluctuate, and this occurs if there is at least one pair of complex conjugate characteristic roots. This can be seen in the trigonometric form of their contribution to the solution equation, involving <span class="texhtml">cos <i>θt</i></span> and <span class="texhtml">sin <i>θt</i></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Solution_with_duplicate_characteristic_roots">Solution with duplicate characteristic roots</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=11" title="Edit section: Solution with duplicate characteristic roots"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the second-order case, if the two roots are identical (<span class="texhtml"><i>λ</i><sub>1</sub> = <i>λ</i><sub>2</sub></span>), they can both be denoted as <span class="texhtml mvar" style="font-style:italic;">λ</span> and a solution may be of the form </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=c_{1}\lambda ^{t}+c_{2}t\lambda ^{t}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mi>t</mi> <msup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=c_{1}\lambda ^{t}+c_{2}t\lambda ^{t}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca68bf80871af0b0da74cf4bae70bd31a71a52ce" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.065ex; height:2.843ex;" alt="{\displaystyle x_{t}=c_{1}\lambda ^{t}+c_{2}t\lambda ^{t}.}"></span> </p> <div class="mw-heading mw-heading3"><h3 id="Solution_by_conversion_to_matrix_form">Solution by conversion to matrix form</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=12" title="Edit section: Solution by conversion to matrix form"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An alternative solution method involves converting the <span class="texhtml mvar" style="font-style:italic;">n</span>th order difference equation to a first-order <a href="/wiki/Matrix_difference_equation" title="Matrix difference equation">matrix difference equation</a>. This is accomplished by writing <span class="texhtml"><i>w</i><sub>1,<i>t</i></sub> = <i>y</i><sub><i>t</i></sub></span>, <span class="texhtml"><i>w</i><sub>2,<i>t</i></sub> = <i>y</i><sub><i>t</i>−1</sub> = <i>w</i><sub>1,<i>t</i>−1</sub></span>, <span class="texhtml"><i>w</i><sub>3,<i>t</i></sub> = <i>y</i><sub><i>t</i>−2</sub> = <i>w</i><sub>2,<i>t</i>−1</sub></span>, and so on. Then the original single <span class="texhtml mvar" style="font-style:italic;">n</span>th-order equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}=a_{1}y_{t-1}+a_{2}y_{t-2}+\cdots +a_{n}y_{t-n}+b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}=a_{1}y_{t-1}+a_{2}y_{t-2}+\cdots +a_{n}y_{t-n}+b}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aed77e3cd0a76363fe2ac5a135474dd6ee1515ad" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:39.524ex; height:2.509ex;" alt="{\displaystyle y_{t}=a_{1}y_{t-1}+a_{2}y_{t-2}+\cdots +a_{n}y_{t-n}+b}"></span> </p><p>can be replaced by the following <span class="texhtml mvar" style="font-style:italic;">n</span> first-order equations: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}w_{1,t}&=a_{1}w_{1,t-1}+a_{2}w_{2,t-1}+\cdots +a_{n}w_{n,t-1}+b\\w_{2,t}&=w_{1,t-1}\\&\,\,\,\vdots \\w_{n,t}&=w_{n-1,t-1}.\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>,</mo> <mi>t</mi> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>,</mo> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo>,</mo> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>,</mo> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mi>b</mi> </mtd> </mtr> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo>,</mo> <mi>t</mi> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>,</mo> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd /> <mtd> <mi></mi> <mspace width="thinmathspace" /> <mspace width="thinmathspace" /> <mspace width="thinmathspace" /> <mo>⋮</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>,</mo> <mi>t</mi> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>,</mo> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>.</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}w_{1,t}&=a_{1}w_{1,t-1}+a_{2}w_{2,t-1}+\cdots +a_{n}w_{n,t-1}+b\\w_{2,t}&=w_{1,t-1}\\&\,\,\,\vdots \\w_{n,t}&=w_{n-1,t-1}.\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a8e35108defd36de5dcb20876b3db85a7dc3e12" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:47.657ex; height:13.676ex;" alt="{\displaystyle {\begin{aligned}w_{1,t}&=a_{1}w_{1,t-1}+a_{2}w_{2,t-1}+\cdots +a_{n}w_{n,t-1}+b\\w_{2,t}&=w_{1,t-1}\\&\,\,\,\vdots \\w_{n,t}&=w_{n-1,t-1}.\end{aligned}}}"></span> </p><p>Defining the vector <span class="texhtml"><b>w</b><sub><i>i</i></sub></span> as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} _{i}={\begin{bmatrix}w_{1,i}\\w_{2,i}\\\vdots \\w_{n,i}\end{bmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">w</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>[</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>,</mo> <mi>i</mi> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo>,</mo> <mi>i</mi> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <mo>⋮</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>w</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>,</mo> <mi>i</mi> </mrow> </msub> </mtd> </mtr> </mtable> <mo>]</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbf {w} _{i}={\begin{bmatrix}w_{1,i}\\w_{2,i}\\\vdots \\w_{n,i}\end{bmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3561745b2f0472760c51c7f3eff408607ab9ffe2" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:13.589ex; height:14.509ex;" alt="{\displaystyle \mathbf {w} _{i}={\begin{bmatrix}w_{1,i}\\w_{2,i}\\\vdots \\w_{n,i}\end{bmatrix}}}"></span> </p><p>this can be put in matrix form as </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {w} _{t}=\mathbf {A} \mathbf {w} _{t-1}+\mathbf {b} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">w</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">A</mi> </mrow> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">w</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="bold">b</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbf {w} _{t}=\mathbf {A} \mathbf {w} _{t-1}+\mathbf {b} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dc9541645bad266cf5b361a73fed83062fa498f" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.059ex; height:2.509ex;" alt="{\displaystyle \mathbf {w} _{t}=\mathbf {A} \mathbf {w} _{t-1}+\mathbf {b} }"></span> </p><p>Here <span class="texhtml"><b>A</b></span> is an <span class="texhtml"><i>n</i> × <i>n</i></span> matrix in which the first row contains <span class="texhtml"><i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>n</i></sub></span> and all other rows have a single 1 with all other elements being 0, and <span class="texhtml"><b>b</b></span> is a column vector with first element <span class="texhtml mvar" style="font-style:italic;">b</span> and with the rest of its elements being 0. </p><p>This matrix equation can be solved using the methods in the article <a href="/wiki/Matrix_difference_equation" title="Matrix difference equation">Matrix difference equation</a>. In the homogeneous case <span class="texhtml">y<sub>i</sub></span> is a para-permanent of a lower triangular matrix <sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Solution_using_generating_functions">Solution using generating functions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=13" title="Edit section: Solution using generating functions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The recurrence </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mi>b</mi> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/341a2d12ce92e3fea7d84164718915a07861be18" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:30.98ex; height:2.509ex;" alt="{\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}"></span> </p><p>can be solved using the theory of <a href="/wiki/Generating_function" title="Generating function">generating functions</a>. First, we write <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle Y(x)=\sum _{t\geq 0}y_{t}x^{t}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>≥</mo> <mn>0</mn> </mrow> </munder> <msub> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle Y(x)=\sum _{t\geq 0}y_{t}x^{t}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5f111d93e0a9ac22d630dd1da18fa391d10c34e3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.899ex; height:3.343ex;" alt="{\textstyle Y(x)=\sum _{t\geq 0}y_{t}x^{t}}"></span>. The recurrence is then equivalent to the following generating function equation: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(x)=a_{1}xY(x)+a_{2}x^{2}Y(x)+\cdots +a_{n}x^{n}Y(x)+{\frac {b}{1-x}}+p(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mi>x</mi> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>b</mi> <mrow> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mrow> </mfrac> </mrow> <mo>+</mo> <mi>p</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(x)=a_{1}xY(x)+a_{2}x^{2}Y(x)+\cdots +a_{n}x^{n}Y(x)+{\frac {b}{1-x}}+p(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dfb9fb5e752928bc6b00148aa9c5955147acc4f2" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:63.428ex; height:5.509ex;" alt="{\displaystyle Y(x)=a_{1}xY(x)+a_{2}x^{2}Y(x)+\cdots +a_{n}x^{n}Y(x)+{\frac {b}{1-x}}+p(x)}"></span> </p><p>where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8cb7afced134ef75572e5314a5d278c2d644f438" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.398ex; height:2.843ex;" alt="{\displaystyle p(x)}"></span> is a polynomial of degree at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd0b0f32b28f51962943ee9ede4fb34198a2521" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}"></span> correcting the initial terms. From this equation we can solve to get </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(x)=\left({\frac {b}{1-x}}+p(x)\right)\cdot {\frac {1}{1-a_{1}x-a_{2}x^{2}-\cdots -a_{n}x^{n}}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>b</mi> <mrow> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mrow> </mfrac> </mrow> <mo>+</mo> <mi>p</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mo>)</mo> </mrow> <mo>⋅</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mrow> <mn>1</mn> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mi>x</mi> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>−</mo> <mo>⋯</mo> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(x)=\left({\frac {b}{1-x}}+p(x)\right)\cdot {\frac {1}{1-a_{1}x-a_{2}x^{2}-\cdots -a_{n}x^{n}}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9166fb3b18c4972fd3290b327610111d15c2c8f8" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:56.437ex; height:6.176ex;" alt="{\displaystyle Y(x)=\left({\frac {b}{1-x}}+p(x)\right)\cdot {\frac {1}{1-a_{1}x-a_{2}x^{2}-\cdots -a_{n}x^{n}}}.}"></span> </p><p>In other words, not worrying about the exact coefficients, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fca9de77ea29879f48f3f08c469fb73b8945a094" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.912ex; height:2.843ex;" alt="{\displaystyle Y(x)}"></span> can be expressed as a <a href="/wiki/Rational_function" title="Rational function">rational function</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y(x)={\frac {f(x)}{g(x)}}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Y</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>g</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mfrac> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Y(x)={\frac {f(x)}{g(x)}}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf587ac4ef25a4ff6870a4e5ffda1a93224b13e9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:13.911ex; height:6.509ex;" alt="{\displaystyle Y(x)={\frac {f(x)}{g(x)}}.}"></span> </p><p>The closed form can then be derived via <a href="/wiki/Partial_fraction_decomposition" title="Partial fraction decomposition">partial fraction decomposition</a>. Specifically, if the generating function is written as <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {f(x)}{g(x)}}=\sum _{i}{\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>g</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </mfrac> </mrow> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {f(x)}{g(x)}}=\sum _{i}{\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/17860f82c35f6d32bdf332fe5c94c0f36464cc45" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.058ex; height:6.843ex;" alt="{\displaystyle {\frac {f(x)}{g(x)}}=\sum _{i}{\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}}"></span> </p><p>then the polynomial <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8cb7afced134ef75572e5314a5d278c2d644f438" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.398ex; height:2.843ex;" alt="{\displaystyle p(x)}"></span> determines the initial set of corrections <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>z</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle z(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3f11ba4d2557380ad85cb695058b70ae697e6e8c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.292ex; height:2.843ex;" alt="{\displaystyle z(n)}"></span>, the denominator <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x-r_{i})^{m}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x-r_{i})^{m}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dbf15cdfdc30fe0bbc504988cd2ad98d14187848" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.503ex; height:2.843ex;" alt="{\displaystyle (x-r_{i})^{m}}"></span> determines the exponential term <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{i}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msubsup> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{i}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0283de44732f903674e0b19b27520b3c0d8e35ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.267ex; height:2.843ex;" alt="{\displaystyle r_{i}^{n}}"></span>, and the degree <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>m</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}"></span> together with the numerator <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f_{i}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/76860d42459c0fb06c73293d257cf90698390262" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.078ex; height:2.843ex;" alt="{\displaystyle f_{i}(x)}"></span> determine the polynomial coefficient <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{i}(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k_{i}(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d9f79643a26051f580599f92fd29f76fef838ea" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.215ex; height:2.843ex;" alt="{\displaystyle k_{i}(n)}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Relation_to_solution_to_differential_equations">Relation to solution to differential equations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=14" title="Edit section: Relation to solution to differential equations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The method for solving linear <a href="/wiki/Differential_equations" class="mw-redirect" title="Differential equations">differential equations</a> is similar to the method above—the "intelligent guess" (<a href="/wiki/Ansatz" title="Ansatz">ansatz</a>) for linear differential equations with constant coefficients is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{\lambda x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>λ</mi> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{\lambda x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f4dc017414386647556fc6f1de9d959cf5371075" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.214ex; height:2.676ex;" alt="{\displaystyle e^{\lambda x}}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }"></span> is a complex number that is determined by substituting the guess into the differential equation. </p><p>This is not a coincidence. Considering the <a href="/wiki/Taylor_series" title="Taylor series">Taylor series</a> of the solution to a linear differential equation: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">∞</mi> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <msup> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>n</mi> <mo>!</mo> </mrow> </mfrac> </mrow> <mo stretchy="false">(</mo> <mi>x</mi> <mo>−</mo> <mi>a</mi> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c116d3aee442eca69ccfaa86b4ac2f1466ae20" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:19.863ex; height:7.176ex;" alt="{\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}"></span> </p><p>it can be seen that the coefficients of the series are given by the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>-th derivative of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}"></span> evaluated at the point <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"></span>. The differential equation provides a linear difference equation relating these coefficients. </p><p>This equivalence can be used to quickly solve for the recurrence relationship for the coefficients in the power series solution of a linear differential equation. </p><p>The rule of thumb (for equations in which the polynomial multiplying the first term is non-zero at zero) is that: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{[k]}\to f[n+k]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </msup> <mo stretchy="false">→</mo> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y^{[k]}\to f[n+k]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c8a1e138fef580dc3d70b4a5156b710e0e302ac6" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.797ex; height:3.343ex;" alt="{\displaystyle y^{[k]}\to f[n+k]}"></span> and more generally <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> <mo>∗</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </msup> <mo stretchy="false">→</mo> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mi>m</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mi>k</mi> <mo>−</mo> <mi>m</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8318210cb2160b4e9addb892ad0bf6b0f79b8766" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:48.668ex; height:3.343ex;" alt="{\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]}"></span> </p><p><b>Example:</b> The recurrence relationship for the Taylor series coefficients of the equation: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mn>3</mn> <mi>x</mi> <mo>−</mo> <mn>4</mn> <mo stretchy="false">)</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">[</mo> <mn>3</mn> <mo stretchy="false">]</mo> </mrow> </msup> <mo>−</mo> <mo stretchy="false">(</mo> <mn>3</mn> <mi>x</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">[</mo> <mn>2</mn> <mo stretchy="false">]</mo> </mrow> </msup> <mo>+</mo> <mn>2</mn> <mi>y</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/88ee5439cae265dc78a697564c2a47e4b297dace" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.352ex; height:3.343ex;" alt="{\displaystyle (x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0}"></span> </p><p>is given by </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mn>3</mn> <mi>n</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">]</mo> <mo>−</mo> <mn>4</mn> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>3</mn> <mo stretchy="false">]</mo> <mo>−</mo> <mn>3</mn> <mi>n</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>−</mo> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mn>2</mn> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6191ee1e6a85a8ed06b771ff51918d1d88834ff" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:78.32ex; height:2.843ex;" alt="{\displaystyle n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0}"></span> </p><p>or </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>−</mo> <mn>4</mn> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>3</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mn>2</mn> <mi>n</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mi>n</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>4</mn> <mo stretchy="false">)</mo> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mn>2</mn> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mn>0.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle -4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e109434a35c75de3113053173ade105aa24b59e3" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.597ex; height:2.843ex;" alt="{\displaystyle -4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.}"></span> </p><p>This example shows how problems generally solved using the power series solution method taught in normal differential equation classes can be solved in a much easier way. </p><p><b>Example:</b> The differential equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ay''+by'+cy=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <msup> <mi>y</mi> <mo>″</mo> </msup> <mo>+</mo> <mi>b</mi> <msup> <mi>y</mi> <mo>′</mo> </msup> <mo>+</mo> <mi>c</mi> <mi>y</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ay''+by'+cy=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b61a1646db7062e31a98c4a84690f9e4345c1309" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.474ex; height:2.843ex;" alt="{\displaystyle ay''+by'+cy=0}"></span> </p><p>has solution </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=e^{ax}.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>y</mi> <mo>=</mo> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> <mi>x</mi> </mrow> </msup> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle y=e^{ax}.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d9a655851b72836e2387e4e57bbaf820967863dd" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.026ex; height:2.676ex;" alt="{\displaystyle y=e^{ax}.}"></span> </p><p>The conversion of the differential equation to a difference equation of the Taylor coefficients is </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle af[n+2]+bf[n+1]+cf[n]=0.}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>2</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mi>b</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>+</mo> <mi>c</mi> <mi>f</mi> <mo stretchy="false">[</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mn>0.</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle af[n+2]+bf[n+1]+cf[n]=0.}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a06b405e70d0f511e5ae2f8216c86a71d49d68ad" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.729ex; height:2.843ex;" alt="{\displaystyle af[n+2]+bf[n+1]+cf[n]=0.}"></span> </p><p>It is easy to see that the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>-th derivative of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{ax}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> <mi>x</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{ax}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c922caffb8d5be4d157a315ce579532f2392e14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.126ex; height:2.343ex;" alt="{\displaystyle e^{ax}}"></span> evaluated at <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}"></span> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2687184a7698e75db65a25bea7afd207bff3d03b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.448ex; height:2.343ex;" alt="{\displaystyle a^{n}}"></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Solving_with_z-transforms">Solving with z-transforms</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=15" title="Edit section: Solving with z-transforms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Certain difference equations - in particular, <a href="/wiki/Z-transform#Linear_constant-coefficient_difference_equation" title="Z-transform">linear constant coefficient</a> difference equations - can be solved using <a href="/wiki/Z-transform" title="Z-transform">z-transforms</a>. The <i>z</i>-transforms are a class of <a href="/wiki/Integral_transform" title="Integral transform">integral transforms</a> that lead to more convenient algebraic manipulations and more straightforward solutions. There are cases in which obtaining a direct solution would be all but impossible, yet solving the problem via a thoughtfully chosen integral transform is straightforward. </p> <div class="mw-heading mw-heading2"><h2 id="Stability">Stability</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=16" title="Edit section: Stability"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the solution equation </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>c</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msubsup> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msubsup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19e1069dbbc1a510d2ba89e4238f10c403f4a785" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.575ex; height:3.176ex;" alt="{\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t},}"></span> </p><p>a term with real characteristic roots converges to 0 as <span class="texhtml mvar" style="font-style:italic;">t</span> grows indefinitely large if the absolute value of the characteristic root is less than 1. If the absolute value equals 1, the term will stay constant as <span class="texhtml mvar" style="font-style:italic;">t</span> grows if the root is +1 but will fluctuate between two values if the root is −1. If the absolute value of the root is greater than 1 the term will become larger and larger over time. A pair of terms with complex conjugate characteristic roots will converge to 0 with dampening fluctuations if the absolute value of the modulus <span class="texhtml mvar" style="font-style:italic;">M</span> of the roots is less than 1; if the modulus equals 1 then constant amplitude fluctuations in the combined terms will persist; and if the modulus is greater than 1, the combined terms will show fluctuations of ever-increasing magnitude. </p><p>Thus the evolving variable <span class="texhtml mvar" style="font-style:italic;">x</span> will converge to 0 if all of the characteristic roots have magnitude less than 1. </p><p>If the largest root has absolute value 1, neither convergence to 0 nor divergence to infinity will occur. If all roots with magnitude 1 are real and positive, <span class="texhtml mvar" style="font-style:italic;">x</span> will converge to the sum of their constant terms <span class="texhtml"><i>c</i><sub><i>i</i></sub></span>; unlike in the stable case, this converged value depends on the initial conditions; different starting points lead to different points in the long run. If any root is −1, its term will contribute permanent fluctuations between two values. If any of the unit-magnitude roots are complex then constant-amplitude fluctuations of <span class="texhtml mvar" style="font-style:italic;">x</span> will persist. </p><p>Finally, if any characteristic root has magnitude greater than 1, then <span class="texhtml mvar" style="font-style:italic;">x</span> will diverge to infinity as time goes to infinity, or will fluctuate between increasingly large positive and negative values. </p><p>A theorem of <a href="/wiki/Issai_Schur" title="Issai Schur">Issai Schur</a> states that all roots have magnitude less than 1 (the stable case) if and only if a particular string of <a href="/wiki/Determinant" title="Determinant">determinants</a> are all positive.<sup id="cite_ref-Baumol_2-1" class="reference"><a href="#cite_note-Baumol-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 247">: 247 </span></sup> </p><p>If a non-homogeneous linear difference equation has been converted to homogeneous form which has been analyzed as above, then the stability and cyclicality properties of the original non-homogeneous equation will be the same as those of the derived homogeneous form, with convergence in the stable case being to the steady-state value <span class="texhtml"><i>y</i>*</span> instead of to 0. </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=17" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Recurrence_relation" title="Recurrence relation">Recurrence relation</a></li> <li><a href="/wiki/Linear_differential_equation" title="Linear differential equation">Linear differential equation</a></li> <li><a href="/wiki/Skolem%E2%80%93Mahler%E2%80%93Lech_theorem" title="Skolem–Mahler–Lech theorem">Skolem–Mahler–Lech theorem</a></li> <li><a href="/wiki/Skolem_problem" title="Skolem problem">Skolem problem</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Linear_recurrence_with_constant_coefficients&action=edit&section=18" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-Chiang-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-Chiang_1-0">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFChiang1984" class="citation book cs1">Chiang, Alpha (1984). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/fundamentalmetho0000chia_h4v2"><i>Fundamental Methods of Mathematical Economics</i></a></span> (Third ed.). New York: McGraw-Hill. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-07-010813-7" title="Special:BookSources/0-07-010813-7"><bdi>0-07-010813-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Fundamental+Methods+of+Mathematical+Economics&rft.place=New+York&rft.edition=Third&rft.pub=McGraw-Hill&rft.date=1984&rft.isbn=0-07-010813-7&rft.aulast=Chiang&rft.aufirst=Alpha&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ffundamentalmetho0000chia_h4v2&rfr_id=info%3Asid%2Fen.wikipedia.org%3ALinear+recurrence+with+constant+coefficients" class="Z3988"></span></span> </li> <li id="cite_note-Baumol-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Baumol_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Baumol_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBaumol1970" class="citation book cs1"><a href="/wiki/William_Baumol" title="William Baumol">Baumol, William</a> (1970). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/economicdynamics0000baum_c7i2"><i>Economic Dynamics</i></a></span> (Third ed.). New York: Macmillan. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-02-306660-1" title="Special:BookSources/0-02-306660-1"><bdi>0-02-306660-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Economic+Dynamics&rft.place=New+York&rft.edition=Third&rft.pub=Macmillan&rft.date=1970&rft.isbn=0-02-306660-1&rft.aulast=Baumol&rft.aufirst=William&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Feconomicdynamics0000baum_c7i2&rfr_id=info%3Asid%2Fen.wikipedia.org%3ALinear+recurrence+with+constant+coefficients" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGreeneKnuth1982" class="citation cs2">Greene, Daniel H.; <a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1982), "2.1.1 Constant coefficients – A) Homogeneous equations", <i>Mathematics for the Analysis of Algorithms</i> (2nd ed.), Birkhäuser, p. 17</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=2.1.1+Constant+coefficients+%E2%80%93+A%29+Homogeneous+equations&rft.btitle=Mathematics+for+the+Analysis+of+Algorithms&rft.pages=17&rft.edition=2nd&rft.pub=Birkh%C3%A4user&rft.date=1982&rft.aulast=Greene&rft.aufirst=Daniel+H.&rft.au=Knuth%2C+Donald+E.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ALinear+recurrence+with+constant+coefficients" class="Z3988"></span>.</span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Chiang, Alpha C., <i>Fundamental Methods of Mathematical Economics</i>, third edition, McGraw-Hill, 1984.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Papanicolaou, Vassilis, "On the asymptotic stability of a class of linear difference equations," <i>Mathematics Magazine</i> 69(1), February 1996, 34–43.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFZatorskyGoy2016" class="citation journal cs1">Zatorsky, Roman; Goy, Taras (2016). <a rel="nofollow" class="external text" href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Goy/goy2.html">"Parapermanent of triangular matrices and some general theorems on number sequences"</a>. <i>J. Int. Seq</i>. <b>19</b>: 16.2.2.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+Int.+Seq.&rft.atitle=Parapermanent+of+triangular+matrices+and+some+general+theorems+on+number+sequences&rft.volume=19&rft.pages=16.2.2&rft.date=2016&rft.aulast=Zatorsky&rft.aufirst=Roman&rft.au=Goy%2C+Taras&rft_id=https%3A%2F%2Fcs.uwaterloo.ca%2Fjournals%2FJIS%2FVOL19%2FGoy%2Fgoy2.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ALinear+recurrence+with+constant+coefficients" class="Z3988"></span></span> </li> </ol></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Linear_recurrence_with_constant_coefficients&oldid=1252039305">https://en.wikipedia.org/w/index.php?title=Linear_recurrence_with_constant_coefficients&oldid=1252039305</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Combinatorics" title="Category:Combinatorics">Combinatorics</a></li><li><a href="/wiki/Category:Dynamical_systems" title="Category:Dynamical systems">Dynamical systems</a></li><li><a href="/wiki/Category:Linear_algebra" title="Category:Linear algebra">Linear algebra</a></li><li><a href="/wiki/Category:Recurrence_relations" title="Category:Recurrence relations">Recurrence relations</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 19 October 2024, at 13:18<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Linear_recurrence_with_constant_coefficients&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-lsb4r","wgBackendResponseTime":167,"wgPageParseReport":{"limitreport":{"cputime":"0.413","walltime":"0.615","ppvisitednodes":{"value":4168,"limit":1000000},"postexpandincludesize":{"value":25526,"limit":2097152},"templateargumentsize":{"value":6267,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":23434,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 378.379 1 -total"," 33.84% 128.028 1 Template:Reflist"," 26.10% 98.750 2 Template:Cite_book"," 23.54% 89.079 1 Template:Short_description"," 18.87% 71.416 37 Template:Math"," 14.47% 54.743 2 Template:Pagetype"," 11.01% 41.653 4 Template:Rp"," 9.60% 36.321 4 Template:R/superscript"," 8.00% 30.262 40 Template:Main_other"," 6.90% 26.127 1 Template:Further"]},"scribunto":{"limitreport-timeusage":{"value":"0.169","limit":"10.000"},"limitreport-memusage":{"value":4920565,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-b49cm","timestamp":"20241122152123","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Linear recurrence with constant coefficients","url":"https:\/\/en.wikipedia.org\/wiki\/Linear_recurrence_with_constant_coefficients","sameAs":"http:\/\/www.wikidata.org\/entity\/Q364089","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q364089","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2016-06-02T02:24:32Z","dateModified":"2024-10-19T13:18:25Z","headline":"relation in algebra"}</script> </body> </html>

CINXE.COM

Linear recurrence with constant coefficients - Wikipedia