Prove Using induction

Let, \(<a_n>_{n \ge 0}\) be a sequence with \(a_0 = 0,a_1=1,\) and \( a_n=2a_{n-1}+a_{n-2}, \forall n \ge 2.\) Prove that,for every \(m > 0\) and \(0\leq j \leq m,2a_m \mid (a_{m+j}+(-1)^j a_{m-j}).\)

#NumberTheory

Note by Tarit Goswami
3 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Induct on j.j. For j=0,1,j=0,1, am+j+(−1)jam−j=2am,a_{m+j}+(-1)^j a_{m-j} = 2a_m, so it's clear. Now if j≥2,j \ge 2, write am+j+(−1)jam−j=2am+j−1+am+j−2+(−1)j(am−j+2−2am−j+1)=2(am+j−1−(−1)jam−(j−1))+(am+j−2+(−1)jam−(j−2))=2(am+j−1+(−1)j−1am−(j−1))+(am+j−2+(−1)j−2am−(j−2)) \begin{aligned} a_{m+j}+(-1)^j a_{m-j} &= 2a_{m+j-1} + a_{m+j-2} + (-1)^j (a_{m-j+2} - 2 a_{m-j+1} ) \\ &= 2\left(a_{m+j-1} - (-1)^j a_{m-(j-1)} \right) + \left( a_{m+j-2} + (-1)^j a_{m-(j-2)} \right) \\ &= 2 \left( a_{m+j-1} + (-1)^{j-1} a_{m-(j-1)} \right) + \left( a_{m+j-2} + (-1)^{j-2} a_{m-(j-2)} \right) \\ \end{aligned} and both the terms in the parentheses are divisible by 2am,2a_m, by the inductive hypothesis.

Patrick Corn - 3 years, 8 months ago

Are you sure you want that 22 there? I mean, this is never true for j=1j=1 since am+1+(−1)1am−1=am,a_{m+1}+(-1)^1 a_{m-1} = a_m, which is not divisible by 2am.2a_m.

Patrick Corn - 3 years, 8 months ago

Log in to reply

Yes , it is 2* a_m ..Ooh! sorry there was a typo in recurrence relation i have fixed it .

Tarit Goswami - 3 years, 8 months ago
×

Problem Loading...

Note Loading...

Set Loading...