3 ms·

For the sequence 1,2,5,14,41,122, I didn't notice that you gained each new term by multiplying by three and then subtracting one. However, the pattern I did not

For the sequence 1,2,5,14,41,122, I didn't notice that you gained each new term by multiplying by three and then subtracting one. However, the pattern I did notice is each additional term is obtained by adding 3^(n-1) where n is the term number. 1 + 3^0 = 2. 2 + 3^1 = 5. 5 + 3^2 = 14. Since these two methods provide the same result, they are probably related somehow, but I can't seem to figure it out.

waterhouse 11y ago
Let f(n) = the nth term of the sequence (where f(1) = 1, f(2) = 2, f(3) = 5, etc). You're saying that f(n) = 3^(n-1) + f(n-1). It also happens that f(n) = 3 * f(n-1) - 1. If we started this sequence with a different value, like 1000, these rules would yield totally different sequences; but it happens that our choice of starting value means these rules are equivalent. Why is this so? It will help to observe that f(n) = (3^(n-1) + 1)/2. Let's check if your rule is then correct: f(n) ?= 3^(n-1) + f(n-1) <=> (plug in observed formula for f) (3^(n-1) + 1)/2 ?= 3^(n-2) + (3^(n-2) + 1)/2 <=> (multiply by 2) 3^(n-1) + 1 ?= 2*3^(n-2) + 3^(n-2) + 1 <=> (subtract 1) 3^(n-1) ?= 2*3^(n-2) + 3^(n-2) <=> (add up multiples of 3^(n-2) on right) 3^(n-1) ?= 3*3^(n-2) <=> (identity) T And then let's check the other rule. f(n) ?= 3*f(n-1) - 1 <=> (plug in formula for f) (3^(n-1) + 1)/2 ?= 3*(3^(n-2) + 1)/2 - 2 <=> (multiply by 2, distribute 3 on right) 3^(n-1) + 1 ?= 3*3^(n-2) + 3*1 - 2 <=> (simplify right) 3^(n-1) + 1 ?= 3^(n-1) + 1 <=> (identity) T (I'm using approximately the proof format described in EWD 1300: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/E...) The totally formal thing to do, rather than "observing" the formula, would be to prove by induction that the formula was correct (i.e. that the given rule, "n -> 3n - 1" with n starting at 1, yields it). How would one come up with the formula in the first place? Generally, if your rule involves multiplying by k every time, then the nth term will probably have k^n in it--though if you started with, say, n = 1/2, you wouldn't get anywhere. Is there a totally generic, plug-and-chug procedure that would yield a formula like this? Approximately, yes. For now, I'll just link to the Fibonacci series: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form

waterhouse 11y ago

Let f(n) = the nth term of the sequence (where f(1) = 1, f(2) = 2, f(3) = 5, etc). You're saying that f(n) = 3^(n-1) + f(n-1). It also happens that f(n) = 3 * f(n-1) - 1. If we started this sequence with a different value, like 1000, these rules would yield totally different sequences; but it happens that our choice of starting value means these rules are equivalent. Why is this so? It will help to observe that f(n) = (3^(n-1) + 1)/2. Let's check if your rule is then correct: f(n) ?= 3^(n-1) + f(n-1) <=> (plug in observed formula for f) (3^(n-1) + 1)/2 ?= 3^(n-2) + (3^(n-2) + 1)/2 <=> (multiply by 2) 3^(n-1) + 1 ?= 2*3^(n-2) + 3^(n-2) + 1 <=> (subtract 1) 3^(n-1) ?= 2*3^(n-2) + 3^(n-2) <=> (add up multiples of 3^(n-2) on right) 3^(n-1) ?= 3*3^(n-2) <=> (identity) T And then let's check the other rule. f(n) ?= 3*f(n-1) - 1 <=> (plug in formula for f) (3^(n-1) + 1)/2 ?= 3*(3^(n-2) + 1)/2 - 2 <=> (multiply by 2, distribute 3 on right) 3^(n-1) + 1 ?= 3*3^(n-2) + 3*1 - 2 <=> (simplify right) 3^(n-1) + 1 ?= 3^(n-1) + 1 <=> (identity) T (I'm using approximately the proof format described in EWD 1300: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/E...) The totally formal thing to do, rather than "observing" the formula, would be to prove by induction that the formula was correct (i.e. that the given rule, "n -> 3n - 1" with n starting at 1, yields it). How would one come up with the formula in the first place? Generally, if your rule involves multiplying by k every time, then the nth term will probably have k^n in it--though if you started with, say, n = 1/2, you wouldn't get anywhere. Is there a totally generic, plug-and-chug procedure that would yield a formula like this? Approximately, yes. For now, I'll just link to the Fibonacci series: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form